...and solved. Yep, it seems to work as expected now. Ultimately it came down to what I had in the Service_Start. I shuffled things around a bit and rewrote small things, and then it started working as expected.
The bad news is that I'm not sure what actually solved this. And I've already spent way too many hours with this problem, and probably restarted my phone more than 100 times. So the best help I can give is to say that something inside Service_Start caused the intent to it to be empty. And just to be super clear: I did not mess with the intent in any way, in my old - broken - code I showed the intent using a toast the first thing, and it showed up as empty.
It doesn't make sense to me, not even a little bit. But that's where I'm at. Hopefully that can be a clue to somebody in the future facing this problem.