Paint high-poly mesh and then bake for low-poly, OR just paint low-poly with normal-map applied?
The upside I can see to that approach might be that if I need to
  adjust the resulting tri-count of the low poly model I don't need to
  repaint - I can just make now low-poly mesh and then re-bake
  accordingly.


Well, you could totally keep your old low poly and bake diffuse onto the new one, which would be basically the same.

To answer you question I would prefer to paint directly on the low poly, for the simple reason that what I see when painting will be the end result, and I don't have to unwrap my high poly. Any texturing software like substance painter is made in order to paint directly on the low poly for this reasons, and others (performance!).
Baking diffuse from high to low poly is useful though, in case where you didn't think you'd need a low poly version, but you find out that you actually do after painting your 'high poly' version.

Another reason might be if you want a very low poly version with lots of normal map details (typically, a robot or mech model with lots of screws and small parts). In this case you would texture every parts and bake normal and diffuse, and then do another painting pass to tie it all together and correct baking issues. You DON'T want to manually paint the diffuse of your normal details when they are already baked.  

Substance painter is able to generate masks based on normal details 'geometry', which allows to texture normal details (I think it's called 'micro-details' in the software) but Blender don't.


  One thing I noticed in painting the low -poly mesh with normal-map
  applied is that occasionally the paint landed slightly off the target
  I was aiming for because of the real topology underneath


I see what you mean, but this might be due to some stretching in your UVs, or worst: overlapping (but you'd know). Or perhaps your texture resolution is too low compared to the details you want to paint.