I too would look for existing modules. LDAP databases (including AD) are commonly used to keep user information and you can find interfaces to them, relational databases or flat files for this purpose. If you search CPAN for user authentication database you will find several existing modules and you can see what best fits your needs.You might also look at what existing application do for user authentication and record keeping.

My inclination would be a user object without database interface, only holding the parameters of a user, and a user collection object with a database interface for persistence. The user collection object would have the search function, returning sets of matching users, and a function for committing a user to the datbase, whether new of changed. But I'm no expert (just opionated) and I would be easily swayed by any well done module.