Don't know if this will help, but I faced the same kind of issue a while ago when my girlfriend replaced her 3GS for a 4S. When texting her, the message wasn't reaching the destination as it was trying to reach the 3GS instead of the 4S. She was able to text me, but I could not answer back, the message being stuck somewhere in Apple's servers.
After a few days of investigation, we fired up the 3GS and disconnected the account on this one, and re-configured the same account on the new 4S. It did the trick and worked as expected since then.
My guess, in that case, is that Apple's server could not handle two devices registered with the same account and the same phone number.
Pretty sure this is not your case, but maybe it will provide you with a hint...
Good luck!