Migrating Office 365 Premium away from Godday

I have just acquired a client who is moving their website away from GoDaddy to a new Domain Host who is putting up a new website for them. The Website vendor wants to host all the DNS records but is not a Microsoft Partner. The company wants to to move their Office 365 Premium subscription from Godaddy  directly to Microsoft. My conversations with Microsoft so far have not been fruit full. They understandablely want to drive this business to their Partner Network. It is only 5 users, not the size client most Microsoft Partners are seeking.

I would think this should not be a complicated issue. But I have found no solution in my web searches and while Microsoft says it can be done the links they have sent me are not related to the issue, but setting up a new domain from scratch and\or migrating from an on premise exchange server. The other solution they suggested was to register and new subscription with Microsoft and then call Tech support and say help. This sounds like a way to foul everything up.

So if anyone has any experience or insight on this I would appreciate some help.

Thanks
Pat