You didn’t need the EU for the removal of trade barriers and the common market. Both were established quite a while before the EU as we know it now became a thing in the 90s.
> we really want those border checks back
Why? You don’t need to be in the EU to belong to Shengen.
The European Union is actually an union of treaties, with countries that sign some and not others. So here you would need to be more specific.