Have you tried hot-start? This procedure has at times (not always, unfortunately) dramatically improved the efficiency and specificity of our PCR reactions from high G + C genomes. Good luck. Steve