I arrived here looking to resolve what I believe to be the exact same issue. I figured I'd post a solution to help anyone else who comes across this.
I have an external drive with 200+ gigs of data, making backing up and reformatting not an option. I was using the little free space I had left to transfer large files between XP and Vista machines, deleting the file from the drive on the target machine after it was copied. After a while there was no free space left and all the regular tricks (disk cleanup, chkdsk, reboot, etc) werent working. I always use the safely remove hardware option from the sys tray before disconnecting the drive every time (I learned my lesson once before).
For those who need some background on recycle bins, see this post. I found it to be a helpful refresher. Sys admin types should know this: http://www.topfreeforum.com/forum/viewtopic.php?p=5694&sid=b76a5f65fe2824d1caaeb2b8a990d033&mforum=neatnettricks
The first thing to try is to empty the recycle bin of the external drive on the machine where you deleted the file(s). You will find that the recycle bin differs depending on the machine you are viewing it from.
If that fails, you can unhide then delete the recycle bin folder on the external drive. In Vista, from a command prompt while in the root of the external drive, enter "attrib -s -h $RECYCLE.BIN". I believe in XP the command is "attrib -s -h RECYCLER". Then simply just open explorer and delete the exposed recycle bin (holding shift). The next time you delete something, the recycle bin will be recreated. If the recycle bin reappears as unhidden, you can re-hide it by using the reverse of that command "attrib +s +h RECYCLER".