Open and run command prompt as administrator on your Windows Server and run the following:

rd /s /q C:\$Recycle.bin

If you have multiple disks/partitions please also run this command for each drive letter by replacing C:\ with your other drive letters.
Example: rd /s /q D:\$Recycle.bin

After this, reboot your computer/server and windows will recreate your recycle bin for you.