I know this is going to sound corny, but sand and paint the surface. Then route the letters.
Now ... take a turkey syringe (available at any major grocery or variety store) and suck up the paint for the routed letters from a can. You cannot use spray paint for this, since the can is pressurized.
Lay the piece flat on a table and s-l-o-w-l-y fill the "well" for each letter you routed out with paint from the syringe, until the paint reaches very near the top of the letter. This will coat the bottom and sides up to the top edge, sort of like filling a swimming pool.
Stop when the paint reaches the top, and let the paint sit there for a minute or two, while you fill other letters. Then use the syringe to suck up the excess paint in the letter or ... drain the pool! Use a Q-tip to remove the remaining drop or two.
When you have flooded and drained the last letter, use the syringe to return the unused paint to the can. Rinse out the syringe with water (water based paint) or mineral spirits or ??? for oil based paint, and clean it up for the next job.