That is a shame, and from a hosting providers perspective, a migration of that magnitude is one headache after another. Now obviously I am a PowerDNN employee so I am a little partial to our service:) We do have free migrations for new customers, which I have long thought was extremely valuable. But from your decision making standpoint, you should really be thinking about what sort of uptime you require, how much support your site may require (this means looking at your use of 3rd party modules and custom code), and how important security is. One you have come up with a good "needs" profile, you can make a decision on a hosting provider.
There are only a couple DotNetNuke specialists around, us being one of them, but there are many hosting providers out there who can host DotNetNuke. As you have probably already learned though, hosting DNN and supporting it are two very different things. When a provider is offering extremely discounted hosting, you can bet that when it comes time to do a hardware upgrade, site migration, or even a datacenter migration, they have to be able to rationalize the support cost. But, if the hosting provider is worth their salt, they will communicate well with their customers, and execute a well thought out plan for any migrations/upgrades.
Goodluck in your pursuits. The great thing about the DNN ecosystem is you always have lots of choices:)