As a first step it would be really helpful if public sector organisations were made to publish the cost of their identity checking. When aggregated this would show how much could potentially be saved. It would also highlight the differences between similar organisations, although cheaper isn't necessarily better here - especially if one cares about fraud and privacy.
The solution isn't as simple as building a 'one size fits all' system analogous to the Identity Card Scheme. Different types of people have very different interactions with the public sector, for example while most families pay council those individuals that pay income tax aren't generally those who claim income related benefits. I'm sure that understanding each citizen, or in practical terms each customer segment, is key to developing a shared service that will work effectively.
Instead of forcing each public sector organisation to make their own cuts more effective savings can be made by focussing on processes, like identity checking, that should be shared. I know that this means that politicians will have to delve into how the government engine they run works - no bad thing in my opinion.