If you delete a user's account on your computer, the system won't remove the trash for that user ID on the external or network drive. This can also happen if you have ever shared a disk between two computers. Since the UIDs on one computer may not be the same as the other, trashes can be created by one computer that cannot be emptied by the other. This can even happen if your username is the same on both computers, but your UIDs (e.g. 501 an 502) are different.
Thus periodically one needs to manually remove the trash like this, in Terminal:
$ sudo -s
$ rm -rf /Volumes/"my_external_disk"/.Trashes/*
$ exit
Replace "my_external_disk" is the name of the disk from which you want to remove all trash from all users. (The quotes are used in case of spaces in the disk name.) I noticed this because I had lost about one-third of my disk space to this phenomena, even though I only had one user account on my present computer.
[robg adds: Be very careful with the rm -rf command -- one little typo could be devastating. To make sure you're deleting the right files first, consider running it with the -i option, which will ask you to confirm each file deletion before it happens.]

