I guess you should look at the start-up folder in the start-menu, just to make sure you don't have anything that will execute this command i.e empty recycle bin or will trigger.
According to what you say it's like it delete items in the recycle bin when the computer starts. So to me i believe it something to do with start-up.
Why don't you try one of the following:
Check the start-up option to make sure no application, shortcut or script can perform this task.
Open the system configuration utility and do one of the following:
Go to start up tab and uncheck any start up item that might perform this task.
Go to General tab and select Diagnostic start-up (in the start up selection section[frame])
Apply and Close.
Restart your system and check to see whether they are still deleted or not.
To open System Configuration Utility
Click the start button and then run and type msconfig
and then OK.
Have a beautiful day and enjoy!!!