So, well getting my handset replaced today, the nice man at Orange, tried one last test with my voicemail, where he left a message, asked me to wait 10 seconds after it gave the delete option, and then delete it (this all being done with my old sony ericsson...). Voicemail indicator disappeared, then I turned the phone off and on, and the indicator reappeared... So as soon as my handset comes tomorrow, I can phone and get a new sim sent. Seems to be the only solution. I'll probably avoid North American roaming as well, as it costs a bomb.