Does your friend still have his iPhone? He needs to put his SIM card in an iPhone with iOS 5, go to Messages in Settings and turn off iMessage - this should fix the problem instantaneously and for everybody who is experiencing the same problem as you.
(I have a friend who frequently turns off iMessage because she's worried about the data charges - I've had her switch it back on a couple times and the change takes effect instantly).
Someone on the apple forums was experiencing a similar issue and posted the following:
"I fixed the issue by putting my sim card back into another iOS5 phone and switched iMessage to "off" which effectively proves that it is tied to your number and not your Apple ID (in my case anyway). I put my sim back into mu phone and the change was instant."