For as long as I've been using Ubuntu (Warty), it's had this problem with certain partitions (especially usb drives). My solution is not really a solution, but it works.
In the Nautilus preferences, under the Behavior tab, turn on the "Include a delete command that bypasses trash" option. Anytime you want to throw something out from the partition in question, just right-click the file and choose to delete. Careful though, because the delete command is ruthlessly permanent.