Re: Both feet, and the ankles
"The problem is that Companies have to be on a preferred supplier list and meet various criteria before they get near to any sort of Government contract."
Yes, but if a small barrier like that is going to stop you contracting probably isn't for you anyway.
I am a suppler to 3 NHS CCGs and am part of the MoD supply chain too (though the MoD one is through a proxy)
There are barriers to doing it, but they are not impossible (or even particularly hard) to overcome.