Re: SAP
If you read closely, IBM was paid $37m - still a big increase but not the $400 million or the $836 million - that big money was probably almost entirely internal - i.e. union & management - costs. So no, this is not 'evil big company screwing naive government agency'. This is just 'SAP is a PITA'.
This type of overrun seems to happen a lot in big SAP systems implementations - the same may be true of PeopleSoft and Oracle, I don't know. People do not realize that 'computerizing' business practices (which is what SAP is basically doing) is a huge undertaking, especially when the organization is large and the business rules are complex, as these Aussie 'wage and work systems' apparently are. You have no idea how complicated your business is until you try to write down the process in the level of gory detail that is required to automate it.
A company I used to work at, with 65,000 employees split between US and international did the SAP thing. Their original plan was to roll out in the US first, then do international. The whole project was to take a year or two (I forget) and about $300 million, of which IIRC $30-$50 million was to go to the vendor (software, hardware, services). By the time the US was done it had taken five years, the cost was over $1 billion. The company cancelled the international rollout, and SAP stock dropped significantly the next day. The additional costs were almost entirely internal labor and training.