are you sure? have you consulted with input nirvana? he seems to be the kinese expert around here.
assuming that's true, vinyl or car paints would definitely be your best bet. i haven't tried rit dye, but it seems to be pretty finicky.
you might first try the most innocuous thing you can think of, to allow for increasingly desperate measures later (lol). for example, you could start with just using a sharpie to write over the legends. if that doesn't look reasonable, you can always dye or paint over the pen marks. i would try a few methods with some laser infilled keycaps from a rubber dome board you don't care about first too.