Blast from the past, I'm going to post in this thread.
Is there anything wrong with not having a "www" entry? Is the redirecting of
http://www.example.com to
http://example.com done in Apache / web server of choice?
How can you have
http://caged.net work, but not
http://randomsubdomain.caged.net (if I read you right, setting @ in the A records would make every random sub domain entry work?