Is your iTunes library on a mounted volume? Seems like you're running into the problem where the Recycle Bin doesn't recognize mounted volumes and thus can't be used. Typically this isn't a problem so much in explorer where you can shift-click to remove files and avoid the annoying message, or use rd /s /q at the command line, but in apps that try to use the Recycle Bin it's considerably more annoying.
In XP there was an option to skip the recycle bin - I do not know if this also exists in Windows 7. Try right clicking on the Recycle Bin in explorer and choosing "Properties" - there may be a checkbox that says something along the lines of "Do not move files to the Recycle Bin. Remove files immediately when deleted." - try using that if it's available.