I know a lot of people are saying that this shouldn't even have to be a step when you switch phones, but the fact is that you chose to use iMessage for the features. It could have been turned off at any time, they are not forcing you to use it.
It would be great if there was a way to fix this without having to call (or unregister your phone number from your apple id), because of not being able to know that it's happening. But it's not like Apple is deliberately trying to keep your messages hostage. Besides, you've already switched phones.