If the system knew both sides were the same vendor or used the same algorithm, would it be better to stream the scene/instructions rather than the video?

I suppose the issue would be media. Faster to load locally than push it out. Could be semi solved with typical web caching approaches.

I've been mulling over the concept of a codec designed for streaming NES video. Stream the VRAM tiles and the RAM data needed to reconstruct the output locally, which could be done in a shader along with CRT simulation if desired.

Very much a one-trick pony, but probably considerably less bandwidth-intensive than even the original resolution (320x224) under nearly any acceptable bitrate.

Are you suggesting to do the 3d rendering on client side, which would require a beefy GPU for the client? The whole point of game streaming is that the game can run on the big noisy, power hungry computer located somewhere else, but the device receiving the stream only needs minimal compute power to decode video.