I'd first double check your Member Management -> Registration Settings to make sure that the proper default group is checked.
that is checked , since most of the new registrant are being registered fine.
That was my first check and it's ok. I even create few users my self, and all were created OK. could not find in which circumstance the new users do not complete the database process.
You can go into member management, search for all users and use the change groups option. You can then choose to add everyone to the Users group and it will do so if they don't already belong to that group.
That part I'm not sure if will work. I did that but I'm not sure. I need to find another member in that situation in order to confirm. The reason is that if I search for that especific member, the ubb threads do not show the member.
I can search by username, displayname or emails and ubbthread never shows the member if the member do not have any group linked.
So I'm not sure if doing that search the way you explain will fix the problem.