I am an O2 Guru and proud Streak owner.... I have had a customer with the exact same problem and it absolutely baffled me, I managed to fix it by playing about with the settings at random but I cannot recall exactly what I did so please bear with me
The other lad was on an iPhone 4 so I had them both come in and set the iPhone to show caller ID (if show caller ID is on on your friends turn it off exit to the homescreen go back to settings and turn it on again), then on the Streak I went into Messages -> Settings and turned on Delivery Reports.
After that we sent 10 messages in a row from the iPhone (1,2,3,4,5,6,7,8,9,10) and they all came through flawlessly.
I think I may have missed a step so let me know how you get on and I will try to jog my memory further!