We had the same issue amplifying RNA libraries from single cells, and ending up with 40% of our library consisting of E. coli RNA from the enzymes. Kapa biosystems claims that this is less of a problem for their enzymes, and they have been better than NEB enzymes in our hands. We also do a short UV cross-linking before using the enzymes.
We also had the issue before and the source of contamination in negative controls we think is mainly from DNA polymerase (or the master mix). DNase treatment and heat inactivation before PCR might help. Another thing you might need to check is the primer stock you have. Once the primer stocks get contaminated by trace bacteria DNA from previous operation or just by accident, you will have contamination all the time. If this is your case, unfortunately you might have to order new primers and make aliquots of your new stocks. Another suggestion is run your PCR less cycles (eg., 30 or 32 cycles) that you also get sufficient product. With that, contamination will never be a problem.
Another trick is to set up your PCR reaction with all but the DNA and treat it with a heat-denaturable restriction enzyme, preferably one that makes lots of cuts. That should degrade any preexisting DNA, and once the enzyme is denatured it won't affect your template or products. I've had that work a few times, but no guarantees.
If its always E. coli DNA its a good probability that your DNA polymerase is contaminated with E. coli DNA. Sometimes when you have home made DNA polymerase (i.e Taq), the purified enzyme is not DNased so you will have DNA in the enzyme mix and give you a positive result every time you do 16s PCR.
Thanks everyone. I have also toyed with the idea of expressing Taq DNA polymerase in S. cerevisiae; a group in Japan reported that this worked for them.
For all who are interested, after careful testing, I have found that Lucigen's EconoTaq is purified to the same degree and has greater activity (as measured by PCR product yield) than Bioron's DFS-Taq.
http://www.lucigen.com/EconoTaq-DNA-Polymerase/
MTP Taq is far more expensive than either of the above.