***Update*** April CU contains the fix - http://blogs.msdn.com/brismith/archive/2009/05/01/project-server-2007-check-in-pending-laid-to-rest.aspx Thanks for all your help!
Thank you all for your continued feedback saying we still haven’t nailed this – and the offers of copies of caches and repro steps. Fortunately we had an internal Microsoft user who read my blog and offered his repro and cache which gave us the benefit of a local repro where we could get at both his cache and his server (Thanks Ken!).
The result of this is a better understanding of where we need to look to resolve this issue and also, with all your feedback, confirmation that even deleting the cache folder (which is now accepted as the best quick fix – as long as your project is REALLY saved and checked in on the server) does not mean the problem will not come back. The problem would appear to be some sort of corruption in the cache that can be re-introduced from a suspect project. Aik now has the smoking gun, and the issue is making its way into our hotfix process (See EPMConnect for other on-demand and Live webcasts).