There's 2 or 3 "permanent" ways. Paint ain't one of them -but- I'd agree that if you're careful, that paint is thick and adhesive enough to tolerate a lot of abuse before it chips, cracks, rubs or just falls off. It may be good enough, ymmv.
Way #1. Hot melt. Few consumer hot melt guns and sticks get hot enough, there's commercial guns which actually use colored HDPE (or PP) to weld to HDPE.
Way #2. Dremmel, or nail or razor or even a soldering gun tip. You're removing some of the material that's already there with obvious consequences for strength.
Way #3. Plasma treatment. I have this for completeness, it's not realistic for consumers
Way #4. Ok, I know I said 3, and even then we need to be loose about what "writing on" means. The 4th way is to use sandpaper to make the surface rough enough so that some of the pigments from a permanent marker gets caught in the nooks and crannies - this could obviously be combined with #2...but sanding isn't writing per se.
I typically use adhesive labels if I want to mark my HDPE bottles, the large surface area gives plenty of contact and the labels I use have a coating (some of the fancier ones come with an additional clear layer, but I typically use a couple of wrap-arounds of 2" wide transparent packaging tape)