In my domain I have the Desktop and My Documents redirected to the file server. I found out that when someone deletes a file from the Desktop it doesn't go to the recycle bin. If you delete a file from My documents it does go to the recycle bin.
They are both redirected using Group policy. Permissions look the same on both folders. My only thought is that because the My documents is redirected to the home folder Windows is acting like it's a local folder and not a network folder.