How about just throwing money at the problem and outsourcing to someone like Trinet? Even if the company doesn't contribute much to premiums, I've always liked, as an employee, having Trinet.
There have also been other less significant issues, mostly regarding my status as a foreign employee. I speculate that it stems from a lack of properly engineered software on their end. In all cases, my problems would have been fixed by some logic along the lines of "If (employee.status == X && !taxesApplied.include(correctTaxes)) then trigger alert Y". Perhaps I'm too much of an engineer, but I find it hard to believe that a company that focusses solely on HR can even operate without this kind of automated check.
Based on your experience, how do they charge (per employee, per transaction, etc) and how much does it cost, roughly?
Not a good look for a company trying to sell a service that requires credibility.
Disclaimer: My data is from an answer to a LinkedIn question several years ago, so it's oudated at best.