As long as you're hardcoding these things, you can try:
RewriteEngine On
RewriteCond %{THE_REQUEST} \ /+729/start-page.asp\?cid=4004($|\ |\&)
RewriteRule ^ /johns-start-page? [L,R=301]
RewriteCond %{THE_REQUEST} \ /+729/start-page.asp\?cid=7916($|\ |\&)
RewriteRule ^ /judys-start-page? [L,R=301]
RewriteRule ^johns-start-page$ /729/start-page.asp?cid=4004 [L,QSA]
RewriteRule ^judys-start-page$ /729/start-page.asp?cid=7916 [L,QSA]
For the subdomains, you're going to need to make sure you have DNS setup to point those subdomains to the same IP address. Then something like:
RewriteEngine On
RewriteCond %{HTTP_HOST} !^johns-start-page\.example\.com$ [NC]
RewriteCond %{THE_REQUEST} \ /+729/start-page.asp\?cid=4004($|\ |\&)
RewriteRule ^ http://johns-start-page.example.com/? [L,R=301]
RewriteCond %{HTTP_HOST} !^judys-start-page\.example\.com$ [NC]
RewriteCond %{THE_REQUEST} \ /+729/start-page.asp\?cid=7916($|\ |\&)
RewriteRule ^ http://judys-start-page.example.com/? [L,R=301]
RewriteCond %{HTTP_HOST} ^johns-start-page\.example\.com$ [NC]
RewriteRule ^$ /729/start-page.asp?cid=4004 [L,QSA]
RewriteCond %{HTTP_HOST} ^judys-start-page\.example\.com$ [NC]
RewriteRule ^$ /729/start-page.asp?cid=7916 [L,QSA]
But all your links could break unless you've set them up to include a FQDN.