RE: What is the strongest glue / epoxy??
I'd be leery of popsicle sticks - what kind of wood are they anyway? Who knows. The sticks I have around feel like they have a waxy coating on them - bad news.
As Daven says - very often it is not the adhesive used, it is how it is used.
Is the substrate clean, grease/oil/spooge free? Oil in the exhaust is a bugger for getting into every nook and cranny. After you Dremel the old adhesive out, can you clean up the area with acetone or MEK?
How well do you mix your epoxy? Some guys I've seen stir it like a cup of coffee, 10 seconds and that is it. You need to remember it is an addition reaction cure - molecules of part A must be in proximity to molecules of part B in order to react. I stir mine, scrape and blend for about two minutes. It takres a bit of energy to truly, thoroughly mix the adhesive well. You'd be surprised how much difference this makes, if you weren't mixing thoroughly to begin with that is.
How accurately do you ratio your part A and B? And don't mix in waxed paper cups either.
You may be doing all this just fine, I'm only throwing things up in the air. As you said, you saw that you did not make contact everywhere, of course that is likely a major culprit.
I am not impressed with the quality of the 15 minute epoxy I have, yet the 5 minute and 30 minute are decent enough. I think it is GP. Use a 30 minute version, make sure you have contact everywhere, and clean materials.