I am not sure in XP, but you may try;

find the recycle bin (not the shortcut) right click on the icon to open the properties of it.
You may accidentally click the button that says: Do not move files to the Recycle Bin Remove files immediately when deleted. If so, just unselect this.