Hi
The obsolete users probably belong to the directory you deleted.
You'll probably find a second entry for each of them that is marked as Current.
It's generally best practise to make sure that you have your LDAP synch very well specified before you actually synch, because of the problems you're encountering. Removing and re-adding directories is also a bad idea. Even worse is removing and re-adding a directory with the same name as the first - this seems to cause some internal confusion (although it may have been fixed in more recent versions.)
The LDAP synch never actually deletes anyone, because that could potentially break referential integrity for historical information related to that user - so it just marks people as Obsolete. Theoretically, if none of the obsolete people have ever been involved in a LC interaction, you could delete the records manually from the database - however, I suspect Adobe support would frown on this (i.e. not support you), and it could potentially cause problems. I'd advise against it.
If this is a fairly new system, with not much data in it yet, I think the best thing you can do is drop the whole database, recreate the database, and start with a clean slate. However, this might not be feasible.
Good luck,
Howard
http://www.avoka.com