I'm not exactly sure what your problem is, if your fat is fried this wont work
You said the directories had garbage filenames. Windows is bad at doing anything with a directory that has funky characters in it. (at least 95 was) and it can be difficult to guess exactly what characters are in the name in DOS too, 'cause some like ASCII#255 won't show up.
to prove my theory drop to the console and type "mkdir abc" then hold [alt] and type "255" which will appear as a space. Try to access it in windows. No luck, eh? and how would you guess there was a 255 in there? (BTW, this technique can be used to hide directories from clueless folks too.)
Anyways, maybe, just maybe, you can still delete these directories.
From your dos prompt run "debug" (I know it sucks, use something better if you can) and find the location of the FAT and list it out. I don't know where to find it but you should be able to read it in there somewhere along with all the HEX values in the filenames. This could be like finding a needle in a haystack unless you do some research first.
Convert these HEX values to decimal and type them in at the DOS prompt as parameters to DEL by holding [alt] and typing the number.
Oh yeah, you MUST type the number of the code on your NUMERIC KEYPAD!
You might have to do this outside of windows all together, I don't know. I haven't used debug for I don't know how many years. Heh, I used to have fun changing the error messages in command.com when I was a kid.
Like I said though, I don't know why your filenames are fscked up. Maybe this will work for you, maybe it won't. Maybe if it does you will still run into problems later, I don't know.
Just my two cents.
Good luck