I have deleted and remove a few songs from my iTunes library and re-sync`d my iphone. After that, I removed everything I have on my computer iTunes library. Then rebooted and re-addes the songs to the library. So, the songs I`ve deleted are no longer on my pc. Re-sync`d my iphone again and they still show up on the phone. How this can be possible ?!
With the later iterations of iTunes, simply deleting a song from the application's library isn't enough, since your music is likely being stored on Apple's cloud storage. You can access your cloud from iTunes or your phone and modify what is being saved. For example, when U2 automatically added their music to everyone's iTunes library, it was stored on the cloud, so you had to delete it from your account's cloud, not just the iTunes library.
Probably backed up on Cloud. Did you check your cloud storage? You can access it by using your computer.