The comments made about the government about excluding IBM from making future systems for the government stood out. The reality is payroll should be executed by payroll specialists. I recently had to research payroll providers and there are players who service 20-30% of the Canadian population already. This is another sign of folks not knowing how to source, design, oversee or implement software implementations.
This is also why Ceridian is still around in spite of all of their faults (or so I hear from any small/mid-size business practitioners I know). I take it that's who you're referring to?
Most have their pros and cons but ultimately can handle complex union type payrolls.
Payroll, also is ripe for disruption.