I'm confident this is a bug and apparently this is where you post.
I had a large functioning city and got bored and decided to just demolish everything and start over there in that plot/city. In the previous city before I demolished it, I had a large hospital with 6 ambulances (didn't turn it off beforehand). I just now realised that since then (and because my finances have obviously changed I now can only afford a clinic), I have no ambulances and everyone is dying! It's as if the 4 I had that were out when I demolished the hospital are ghosts now. To test this, I demolished the clinic and placed a hospital.. still, there were no ambulances but once I placed the bay to add two additional ambulances (supposed to be 6 total now), I now have two that will go out responding to emergencies.
I've restarted my game numerous times so I know it's not something that will be resolved by kind of "reloading" the city.
This is a bug of bulldozer tool, that had not been fixed since 10/3/2013 as far as I know.
If you bulldoze any manually placed building with some service cars not in the garage/ deleting any module with some cars away, the car will be lost forever until they fix the bug