We use PayCycle. It is $42.99 + (numEmployees - 5) * 1.50 per month no matter how many checks you generate. This means you aren't penalized for paying weekly or for generating reimbursement checks out of phase with your normal payroll cycle. I really like it. It generates export files which I import easily into QuickBooks.
I'm very happy with it, I just wish it had an API so I could plug my timesheet system directly into it. Presently I have to transcribe from a web report into their interface but as we only have 16 employees total, it is not a big burden.
We evaluated ADP and they were much more expensive for our use case.
Is their system browser based as well? If so, seems like a clever Greasemonkey could greatly help with that automation (might need an temporary cache there somewhere).
Scrape your web report, stuff the data somewhere (locally), then on their site, read your cached data and populate their forms.
Yes, I should have used max(). I copied that expression out of my budget spreadsheet and I added that cell after we had 5 or more employees, apparently.