How do you recover a Deleted Recycle Bin (Win XP)?

One of my clients has managed to delete his RECYCLE BIN. No, not just the icon, but the entire bin. Windows Explorer does not show it even there on the tree.
RegEdit tricks used by TweakUI and other tools do not bring it back. I have even walked through all the items in KB810869, but to no avail. The user did not tell me about it for over 2 months, so there is no restore point to fall back on. Also, he is 400 miles away, so I will need to resolve this remotely (via LogMeIn).
Any thoughts?