This is one of the those little problems that everyone, with an iPhone/iPod/iPad, encounters someday: you delete a song from iTunes, then you connect your iDevice to the computer and do the synchronization.
For some reason, the deleted song reappear, both on your mobile and on your computer.
What a damned nuisance!
The reason
iTunes tries to keep all your devices in sync, bi-directionally. If something is missing, is recovered from the device that still has the content and replicated on others. What you are deleting it from iTunes is restored from your iPhonePodPad.
The fix
It’s very easy: just synchronize them (just to be sure that every other contents is ok on both side), delete that damn song from your iTunes and synchronize again, immediately after. You’ll see iTunes asking you to transfer some missing contents, warning you that if you don’t do it now, these contents will be permanently deleted from any other devices that you usually synchronize. We know that the “missing content” can be only the song we just deleted, because it’s the only difference between the first and the second synchronization we did, so choose to not transfer it. Et voilà! The song is gone forever.
If you have more of one Apple mobile device, just repeat the procedure for everyone.