I emailed Google about removing my domains, after a few emails exchanged (the first couple were generic "how to" delete your Google Apps account), they went ahead and removed my domains from their Google Apps verification system. Now my jabber accounts are working perfectly with Google users again.
Now this problem occurred with all 11 of my domains hosted at Dreamhost (with Dreamhost being a registrar/host for some and only a host for others). A couple of the domains were literally added to Dreamhost's server 2 weeks ago. These are unique domain names that nobody even knew existed so I doubt that any regular "stranger" on the Internet added them to Google Apps verification system.
After conversing with Google (and not mentioning that my domains are at Dreamhost), they responded with this:
"We have removed all the Google Apps accounts for the domains that you specified in an earlier email. Please note that these accounts were not provisioned by us, but rather dreamhost.com."
Dreamhost support has no idea why this happens and can't fix it on their end. But from what I've gathered (from the timing of the domain registration/host, others having this problem, and Google mentioning Dreamhost), it looks like the problem does lie on Dreamhost's end. Here's hoping they figure out the problem soon.