I know what you mean... I just purged almost 4000 accounts from my system to get it up and running again.  If nothing else, we're at least narrowing down the symptoms significantly, which should help greatly with the trouble-shooting.  Right now I'm thinking along the lines of user account table corruption of some sort...

Hi guys!

I just deleted one dnn user which also exist in our AD. After that, I have manually created exact the same user in DNN, with random dnn password. When this user logoff/logon to windows and browses to dnn site, he must provide username/pass. AD password works, so AD pass synchronization works well. But why this user MUST type his password for the first time???

I did a restructuring of my configuration before I did this.  First I made sure that all DNN security roles used for editing had a matching AD group, and then made sure the correct people were in that group.  Then I went into a SuperUser account, and did a query like this:

update userportals set authorised = 0 where userid in (select userid from users where username like '%domain\%')"

Then I went in and deleted all unathorized accounts from the Admin->User Accounts menu (took a couple of tries due to the sheer volume).

I chose to do it this way to make sure DNN did the proper cleanup of user accounts, seeing as the information seems to be spread across several different tables.   With the matching AD groups, I shouldn't have to do any manual creation of accounts either. 

So far it has worked out well, there were a couple of problems with doing this, and those were with modules that based thier settings off of the userid field which changed when the account was re-created.  Overall it went pretty smooth.