who actually negotiates these big public sector contracts?
Well, the Govt have a procedure for inviting bids for these things. The companies make promises in the bids, some of which may not be reasonable or at least highly optimistic, but they generally make sure their arses are covered, as kimbers says.
The bottom line is this: Government agencies are generally staffed by people who joined 20 years ago straight out of uni looking for a nice safe easy job. They know how passport applications work or company legislation, but not much else. And they know naff all about IT. So they say 'we want X and Y' without really understanding the implications, or having any idea if X and Y are going to be any good. The IT companies then have their salespeople bid for the contracts with the 'customer is always right' attitude so they say yes to everything, on any timescale.
Then when it comes to implement it, you have actual techies trying to extract proper information from the fairly clueless low level agency staff and finding it rather hard, because the staff don't understand IT. But the IT people can't push back and sort the problems out because the high level people have already signed off the requirements that turn out to be unworkable due to either timescales or lack of insight and information. The people higher up the management chain don't understand what the issue is, why can't these idiot techies just DO IT? They then generally cover up the problems on the assumption they can be solved, and report up to their bosses that things are ok.
Basically. the problem is lack of understanding of the system and requirements by the agencies themselves, and the IT companies are generally happy to do the work because their arses are covered and they can pin the blame on the agencies.
This is really PPP of course at it's worst, but since it's been this way for a long time no-one's bothered about it as they are for stuff like the NHS. What the UK really needs is a Government IT agency to bring everything in-house. At least then it'd have expertise to be able to figure out what it needs and move forwards, and the long term IT resources to be able to develop the solutions.
An example of the kind of short sighted attitude from agencies: Years ago, to make changes to your registered company, you had to send in forms. The legislation was recently overhauled with new forms, and a new system built at great length and expense from scratch for processing forms. Why? Why use forms at all? Why can't I log onto a webpage and simply edit the details directly? It'd have been vastly quicker and easier to implement, and better to use too. But goverment agencies process forms, that's what they do.
Note that this rant is not about any project in particular, just in case anyone's snooping around.