How are you handling payroll withholding? Nearly every major nation has some equivalent of this. What about income tax withholding for cross border payments?

These are issues that even the most basic payroll services offer today (i.e., handling the actual withholding/deductions and remitting the proper amounts to the relevant tax authorities, not just keeping records). If you're not addressing the tax issues, you're product isn't dead simple--it actually increases the complexity of paying employees dramatically. Withholding taxes, for example, are due at least quarterly; payroll taxes are usually due at least monthly.