[sjau]

You can create a wildcard entry for the subs and point it to the domain or your IP in the dns...

*.domain.com.      IN  A    1.2.3.4

Then in the apache config create something like this:

    DocumentRoot /www/domain/html
    ServerName www.domain.com
    ServerAlias *.domain.com

And then you only need a .htaccess with rewriting... something like this should work

RewriteEngine On
RewriteCond %{HTTP_HOST} !^www\.domain\.com [NC]
RewriteCond %{HTTP_HOST} ^a(.*)-01\.domain\.com [NC]
RewriteRule ^(.*) /A%1/$1 [L]