O Fedora, que é bastante RedHatty, parece registrar o uso de useradd, mesmo quando invocado pelo root (ao invés de via sudo, que naturalmente também deixaria logs):
[root@anni log]# useradd foo
[root@anni log]# tail /var/log/secure
Sep 13 16:15:15 anni useradd[17621]: new group: name=foo, GID=502
Sep 13 16:15:15 anni useradd[17621]: new user: name=foo, UID=502, GID=502, home=/home/foo, shell=/bin/bash
Por quanto tempo você mantém cópias antigas de /var/log/secure
é uma questão para você e sua configuração do logrotate.