I spoke to Orange about it and they weren't much help (they accused O2 of having a problem because my wife was recieving them twice. Lame).
I'm now waiting until my next bill so i can check if I'm being charged twice (If I am, they can look out! :twisted: ) but I think I may have worked something out.
I noticed that if I write the message, send it and close the inbox immediately then I don't get a 'sent' notification (until I re-open the inbox). When I send a message and leave the inbox open until i get the 'sent' notification then it works fine. Not ideal, but hey, it's a fix!
Just thought I'd mention it in case anyone else has had this.