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?
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.