You could get em sandblasted and powder coated, I did it with mine and they've come up a treat. I got em done in Satin Black. It's not that expensive either if you find the right place. Most powder coaters should be able to blast em first for you. If you end up just painting them just use the normal prep for painting, clean all the rust and dirt of them, give a sand with 120 grit to rough up the chrome, a couple of coats of primer (light sand between coats with 600 grit) and a couple of top coats (sand between) The more top coats and light sanding, the better they will be. I may still have my black, non rubber ones, at home somewhere off my mk 2, i'll have a look for ya.
Cheers, Richo