Remember, if you just delete the profile files and not the accounts, you can
recover/restore the files from the Recycle Bin.
If you deleted the accounts (and not the files), then when you recreate the
accounts, XP will create a new profile folder under Documents and Settings
folder for each new account.
Say the old account name was Bob.
If the folder is still there, when you recreate Bob's account, XP will give
the profile folder a name like Bob."computername"
Open Windows Explorer. Click Tools, Folder Options, View tab, make sure Show
Hidden Files is selected.
After you recreate all the accounts on the computer, reboot.
Login once for each account created to let XP build a new profile folder.
Reboot the computer and login as Administrator
Open Windows Explorer.
Expand the Documents and Settings folder.
There should be a folder for each account.
Take one account name at a time. Open the original account profile folder
and copy all the contents.
Select the newly created folder for that account and paste those files
there. Yes to overwrite all.
After you have all the accounts restored, you can delete the original
profile folders and empty the recycle bin.
I would recommend a Defragmentation after doing this.