Rather than telling your friends to delete their entire history, what's the problem with asking them to just make a new contact listing? I'm not familiar with the gubbins of iMessage.
I think the problem is that asking everyone that's ever messaged you from an iOS device to modify something on their handset every time someone in their contacts switches platforms isn't a reasonable request.