Not an issue I have now, luckily, as I've switched hosts, but this annoyed me for a while.
I had a site hosted with a host who did not give me a DNS control panel, just cPanel. Is there a way using cPanel to set up Google Apps for Domains for email?