Google does something similar when you apply for Google Apps for your domain. They have a long list of hosting companies and how to configure your domain with them to make it work.

Now, I can tell you, after suffering 3 of them, I decided to go for he VPS option.

So, did you get a solution?