It is the M- F-ing supercoiling!!!
During my PhD I successfully used BamHI a lot & found it was very forgiving (i.e. lazy massive over digests over night at 37oC with no problems during subsequent cloning).
However, having moved & started a Post-doc, my BamHI digests suddenly stopped working. I was performing multiple BamHI digests & still getting 100s of colonies on my negative control plate (simply the purified vector without insert, ligase or even ligation buffer). It was a small comfort to find this forum and that a minority of people had be experiencing similar problems. However, I tried the suggested comments to no avail (i.e. being very careful about over digestion/volumes/etc)
When I ran my digests out on a gel, they ran as a single band (as expected). The uncut vector runs as two bands: Predominantly as an upper 'relaxed' band (running at higher MW than cut band), with a small amount of supercoiled plasmid, which unfortunately ran at same MW as my cut plasmid. Following BamHI digestions, the former band completely disappeared suggesting a good digest, however I couldn't be sure the supercoiled plasmid was being digested.
So what I did was gel purify my plasmid pre-digestion, ensuring only to extract the bands corresponding to the 'relaxed' form. Then I digested with BamHI, treated with CIAP & purified (NB: I simply column purified here, I didn't gel purify a 2nd time).
100 ng of vector treated this way yielded no colonies (I did it side by side with 100 ng of vector not pre-purified and this yielded 100s of colonies as before).
I concluded that the supercolied plasmid was resistant to BamHI.
Now, I know from my PhD that BamHI is not so ineffective against all super coiled plasmids, clearly the vast majority of people have no problems performing BamHI digests on plasmids. I only have a very basic understanding of supercoiling, but I imagine that there must be a minimum number of kb to accommodate a writhe regardless of twist. I propose that if you are unlucky enough to have a plasmid that just isn't large enough to accommodate an additional writhe (& therefore retains the maximum amount of tension on the DNA) BamHI (& possibly other enzymes) have difficulty cutting.
I am sure people who are better versed on supercoiling than me will have a lot to say about this. However, all I know is that gel purifying my plasmid pre-digest completely solved this problem.