Here’s an idea for GNOME 3.x. Instead of showing a static wallpaper, start treating the wallpaper as an infinite plane. Basically instead of using a JPEG or PNG file as input, build a library that given a rectangle returns the image data (raster or even better vector) corresponding to the surface it covers. As monitors and workspaces come and go, the shell can expand and contract the background, calling the library as needed to build the missing parts.
The possibilities are endless. The easiest implementation is an infinitely tiled texture. Another could be a photo wall with randomly rotated and scaled faux-polaroid versions of your Pictures. Or take pre-defined sets of vector cliparts as input. Whatever is visually pleasant and results in a background unique enough to give subtle hints as to the current position on the plane. By “learning” the wallpaper, the user will subconsciously know where he is and where his windows are.
Add parallax scrolling. When switching to the next workspace, only scroll the wallpaper by a fraction of the size of the workspace. Say 50%. This will add to the perception of depth (wallpaper being non-interactive) while the uniqueness of procedurally generated workspace will give hints about both the current position in the workspace stack and the contents of the adjacent workspaces (as they share parts of the background with the current one).
Profit?
I love the idea.