I did a clean install (of C: only). And I am currently running programs from E: that were installed a week ago. One example is a game. However, it was installed through Steam, which resides on E: as well. Maybe that's the difference?
I guess I'll just try to delete everything about a program when the time comes.
You're right, Steam installs things on the same drive as it. As for the other programs, I don't believe you'll be in trouble if you delete the folders of the programs one by one, or even in bulk.
As far as I understand, when Windows installs a program, the program creates lots of keys in the registry which Windows accesses. However, a fresh install will remove the registry.
Thus, although it's never advised to uninstall a program just by deleting the folder usually, in your case, you can.