Nokia 3100 / 3120
Outlook Express on my PC, but no absolutely sure.
I think it is a software fluke, but working with the Nokia Tech to do several things to try to reset the Headset Icon from appearing didn't help. Had to send mine back for replacement. Luckily in was under warranty.
BTW, I had never used a headset with my phone. I have seen this problem complained about by other users on the net. You may be able to convince Nokia to replace it even if it is out of warranty because it is a software problem I think and not a hardware, and it is a common design problem it seems.