This doesn't address the lost files question, but you can copy profiles from other machines on NT4 & I assume 2000. Of course, they'd have to be similar/same to be useful. In NT, r-click My Computer, Profile tab & choose copy.
Otherwise, you'd have to use some kinda file-recovery program for the lost directories/files, and if much disk I/O has occurred since the delete, it'd be almost impossible.