I had the same request last fall so what I did was setup a new instance with only the payroll user (it's a SQL account not NT, I'm sure not all payroll programs are like this but our's is).
There are no other NT accounts or groups setup, the BuiltIn/Administrators has been removed from sysadmin role.
So basically there is me(the only DBA), the sa account(password resides only in my head and a sealed envelope with the HR manager) and the payroll user that can access the instance.
Then to instill confindence about the security I enabled C2 auditing. This only works if you have the disk space for the trace files and time to monitoring it.
They still have to trust me but the C2 auditing tracks every login and data access no matter who does it.
It may not work for you depending on resources but my payroll department is happy with the solution.