This is actually easy to solve -- most VNC applications already implement the solution, which is to have a local, lag-free cursor that is shown to the user, and hide the laggy cursor on the other machine.

One thing I forgot to mention in the post is that there is apparently an OnLive API that some games are using that replaces the cursor in the game with a local cursor. Not all games can use it (for example, World of Goo's cursor is blocked by walls and such which is critical to gameplay), but Unreal Tournament, and OnLive itself, use it in the UI.

Edit: of course this wouldn't solve the case where you are actually doing something in Photoshop that might require real-time feedback like the airbrush tool!