Indeed, the answer is Rema. There may be some other brands that are as good, but Rema forms an actual chemical bond between the patch and the rubber of the tire. The vulcanizing fluid prepares the surface of the tube so it will bond to the patch. Better living through chemistry.

Everything else, check. Roughing up the patch area, waiting a few minutes for the vulcanizing fluid to dry, squeezing the patch for a few seconds after applying.

I've never had a problem with the little sandpaper that comes with the kit.