On OP's particular issue: I'm surprised he didn't mention paycycle (now part of intuit). I went with it due to similar concerns (as well as it clearly being the cheapest).