It would be inefficient, but not necessarily prohibitively so if you're talking about the kind of business where piracy is a serious problem so there is real money to spend.
There's also quite a few things out there for removing video watermarks
If you're operating on the kind of level we're talking about, you don't just put in a visible watermark, you convert the entire file/stream to embed a unique forensic footprint tied to the account of whoever downloaded it. Such a footprint will stand up to just about any manipulation you can think of that doesn't reduce the quality of the data so much that the value is destroyed anyway, and you're probably not removing it unless you have a PhD or two in the field and you know someone's secret key.
The limitation with any watermarking approach is that fundamentally it's still based on the honour system and obviously does nothing to prevent private copying between people who don't care about ripping someone off. It's not a technical limitation.
Motorola's (Google) new gear can do this, though the purpose is targeted advertising not watermarks. The truth is streaming DRM is about preventing your mother from giving a copy to the neighbors, almost all the content is already on P2P by the time it streams.
Real time gaming is not streaming video...
[1] Like various Avisynth plugins for example: http://avisynth.org/mediawiki/External_filters#Logo_Removal