I have managed to get some of the way along with the following Apache rewrite, using mod_jk2 to forward to Tomcat with Confluence installed as /. I have a mapping file to translate the domain name into a space key.

RewriteEngine on

1. Set map to convert to lowercase
   RewriteMap lowercase int:tolower
2. Set map type and path
   RewriteMap vhost txt:/etc/apache2/maps/vhost
3. HTTP_HOST not blank
   #RewriteCond %{HTTP_HOST} !^$
   # Convert HTTP_HOST to lowercase
   RewriteCond ${lowercase:%{HTTP_HOST}|NONE} ^((dev|stage)\.)?(.+)$
4. Search for host in vhost map
   RewriteCond ${vhost:%3} ^(.*)$
5. Prefix path with vhost search result and set environment variable "VHOST"
   RewriteRule ^(.*)$ $1 [E=VHOST:${lowercase:%{HTTP_HOST}},E=SPACE:%1]

RewriteRule ^/display/\w+(/?.*) $1 [R,L]
RewriteRule ^/display/(~.*) /user/$1 [R,L]
RewriteRule ^/$ /Home
RewriteRule ^/(styles/.*)$ /$1?spaceKey=%{ENV:SPACE} [QSA,PT,L]
RewriteRule ^/user/(~.*)$ /display/$1 [PT,L]
RewriteRule ^/(decorators|pages|images|spaces|download|x|rpc|admin)(/(.*))?$ /$1/$3 [PT,L]
RewriteRule ^/(.\.action.)$ /$1 [PT,L]
#RewriteRule ^(/display/%{ENV:SPACE})?/(.*)$ /display/%{ENV:SPACE}/$2 [PT,L]
RewriteRule ^/(.*)$ /display/%{ENV:SPACE}/$1 [PT,L]

It would be nice if this could be done a little cleaner e.g. pass the space key as a querystring parameter to every request or prefix every URI with the space key e.g.
/display/Home?spaceKey=<space> or
/<space>/display/Home or
/styles/<space>/Home