The original adhesive was the clear pressure-sensitive type. The adhesive residue itself is part of the problem with getting it to stick again with anything else. You're fighting with not only the adhesive that let go on the surface of the car, but it's also slowly letting go of the sticker material as well. So you get part of it down, and then more of it lets go under the tension of the curved surface and a sticker that wants to flatten out.
Here's another option to try -- 3M makes a spray adhesive which lays down clear... Permatex also makes a version of the same product, I believe. Normally you spray at least one surface, let it stand for a minute or less to get tacky (it lets most of the solvent flash off) and then apply. (Applying to two surfaces makes for an even stronger bond.) It dries transparent and with no significant buildup, just like the old pressure-sensitive adhesive. Spray some onto a metal can lid or clean, smooth flexible plastic lid (like some butter tubs or Pringles cans have). Make a nice puddle of the adhesive. Then use a little foam applicator -- the kind used for eye makeup -- and/or wooden toothpick to pick up some of the adhesive and work some onto the surface of the sticker that's lifting. Wait 30 seconds to a minute and then squeeze it down, wiping away any excess that squeezes out carefully. The excess tends to stick to fingers really well, so wipe your fingers well before you go back and squeeze more out. Unless the sticker is really determined to curl away, it should stay down and the adhesive will set.
For stickers where the whole of the pressure-senisitve adhesive is giving up/drying out completely, the 3M/Permatex spray adhesives work well as a replacement. Clean off the old adhesive from the label and the surface it was stuck to, then spray on the new adhesive and apply.
