A) A set of tools to talk with external systems B) A set of tools for manipulating the internal representation of payroll data C) A GUI for interacting with / managing the system.
When their internal process is simple managing the payroll system should be simple. When their internal process is complex you get fat consulting checks. Which brings up a great point, it seems like large companies that simplify their internal systems could avoid writing a lot of consulting checks, so I suspect they must be out there and you just don't hear about.
1) There is "one" way of representing payroll data. There's not. When you get a none trivial amount of clients, all their edge cases put together destroy any ability to fit the data into one conceptual model elegantly.
2) Companies have control over payroll rules. Large companies often can't simplify their systems due to contracts or the subsequent employee mutiny. Unless you want to get sued, lose the lawsuit, and pay out the nose (which I've seen happen), you can't just change how you do payroll on a dime.
Not to mention, there's a ton of disfunction too. Payroll managers aren't always the brightest tools in the shed. One project I worked on lead to the payroll manager getting fired over "bad stuff" I uncovered. And then as I uncovered more stuff his replacement was let go too.
...payroll can be a total clusterfuck. Avoid at all cost.
2) I would argue that much of this complexity shows up because many companies negotiate while ignoring the cost of adding complexity. Company wants to minimize cost, workers want to maximize benefits, complexity is a dead weight that benefits nobody. Once things have been negotiated it's hard to change, but during negotiation they is no need to end up with yet another edge case.
PS: I don't think organizations end up spending 100+ million on their payroll systems because it's easy. I just think being proactive lets some companies minimize those costs. EX: Is Google's payroll system ugly?
That said, there are ways to develop payroll software that keeps extension possibilities and accommodate the variations without disrupting the engine.
Long story short, I agree with what you're saying, but you make it sound like it's really simple.
It's not.
Creating a single payroll solution to handle one company is very easy. Creating a single payroll solution to handle many companies is also quite doable.
But once you get to the scale of ADP, it's impossible to handle everyone elegantly. Between union contracts and non-standard practices, there are (what felt like) an infinite number of things a customer can throw at you, with one rule wackier than the next.
It's damn hard to write a generic payroll solution that handles most companies. Damn hard.