It sounds like you should have moved from MySQL to PostgreSQL instead of switching hosting providers.
Otherwise, heartily agreed.
If you don't mind my asking, is there some key feature of Wordpress or its plugins that holds you to it? I'm always interested to hear why people stick with it.