You are trying to use cascading combos boxes. You will have this issue not only with datasheet mode, but also with continuous forms. It has been this way for a long time in Access.
Check out this page by AWF member LPurvis: Downloads (click here)
Look for Continuous Form Combo
The example handles exactly what you need, but I think it only works with continuous mode.
AFAIK, you will not be able to use datasheet mode. You will need to switch to continuous mode. I almost never use datasheet mode. It just has to many limits.
Sorry but it must be me being stupid. The example at the link you sent me doesnt seem to work. Shoul I expect the Service Combo to change when the Category Combo changes? It only changes if you force a refresh.