Yes, GPOs are the best way to go.
If you can't/won't use GPOs, there a tool that can delete profiles:
DelProf

But if i understand it right, you have a bunch of old profiles on your profile-share, and the useraccounts which they belonged to are already gone?
Mhm, that would be not an fast and easy task, but depends on how many profiles you got, if its faster to do it manually. For the future i would implement somthing that deletes them automatically if a user gets deleted.

If it has to be scripted, you would need to read all users from AD, read all the folder names and compare them to each other. At least for the first two tasks (if not for all) you find UDFs here in the forum, for the third i could help you.