OK, I've implemented this feature using cross-platform send2trash library. Now by default we delete to trash.
If there is problems with Linux behavior, then please make sure they fixed upstream, don't blame explorer if it does not conform your distributive stadards. On Windows (and I suppose on Mac too) it works very nice.
For reference: http://pypi.python.org/pypi/Send2Trash/1.2.0
I've bundled copy of this library into explorer with modifications to get python 2.4-2.5 compatibility.