Have you changed any of the Windows default sound options? (Control Panel->Sound->Sounds) Try loading the Windows Default scheme.
Have you changed any notifications? (Control Panel->Notification Area Icons) There is one called Windows Explorer which is used for safely ejecting removable devices. Mine doesn't show a visual notification when I add or remove anything that's been used on the system before, or anything that has drivers. When I plug in something new it may install drivers. I have it set to 'Only Show Notifications' here.
Have you changed anything in Autoplay? Even with 'Use Autoplay...' disabled and 'Removable Drive = Take no action' I still get sound notifications. However you can change this to 'Ask me every time' to at least show a pop-up in the upper-right of the desktop.
The only way I can get new device sounds to stop is by changing the sound option for 'Device Connect'. The second two options are long shots to fix the problem as a Windows issue, but with Autoplay, at least for some devices, you ought to be able to get a visual notification every time. (I would choose 'Ask me every time' just because I am paranoid about auto-running stuff, even Explorer, for security sake.)
Other thoughts - is there any pattern? Is it certain devices only? Do you have any other programs that take over the sound output? (I usually run Foobar music player this way...no system or other program sounds are played unless music is stopped, not just paused.)
p.s. Is Core Parking enabled or disabled?