Now then.... That adhesive they include has to be the crappiest I have ever seen. Any good recommendations for a replacement?

I agree. When double-sided adhesive tape didn't work, a moron who installed my old Kenwood head unit used some kind of cyanoacrilate. Of course, it is not meant for application like this and cracked in few days. I ended up using several drops of clear silicone putty. Actually, I use it elsewhere in the car (e.g. to hold a box of tisssues), because, while it sticks well enough even on textured or curved surfaces, it is easy to remove without leaving traces.The only problem is that one has to hold the object being glued for several minutes while the putty polymerizes.