Solved it, sort of…
The problem is related to a bug I reported about 18 months ago (to which I got no official reply from Steinberg…big surprise 
) in this thread.
Anytime you so much touch anything in the CMC-AI template editor in: Devices → Device Setup → Remote Devices, you need to go to Devices → Device Setup → Remote Devices → Your Generic Remote template and press the ‘reset’ button to get it working. This also needs to be done manually everytime you start Cubase.
Would be nice if Steinberg at some point decided to fix their buggy implementation of Generic Remote in conjuction with (their OWN!) CMC controllers in their (OWN!) Software…