The Recycle Bin on XP for each file system is in the (hidden, system flagged, etc.) "RECYCLER" directory in the root (i.e. C:\RECYCLER). Going there may not give you a fancy "empty recycle bin" option, though. I don't remember. You'll have to enable the show hidden and disable the "hide system files" options for it to appear.
Even if it's hidden from the desktop, I thought it would still show up in the explorer tree view, though. I've you've got all the shortcuts for that hidden, just hit Win+E (hold down the "windows logo" key and press 'E'). That should bring it up even on a very stripped down Windows build (it works on a stripped down XP embedded build I played with that didn't even have notepad!).