iMessages go through Apple's servers, right? Then if all messages addressed to a particular phone suddenly stop being delivered, surely they can detect that. If a phone fails to check in for some period of time, there's a pretty good chance that the user has switched to a different device, and the messages should be retransmitted as SMS. Even if the timeout is on the order of days, that would still be better than having your messages swallowed by the void forever.

For bonus points, take care of false positives in this system by storing enough metadata in iMessage to deduplicate the iMessage and SMS copies.