What my friend did was to leave the bases black, but paint one big drop onto each one in a different color. So if there was an orc tribe, there would be Orc Green, Orc Blue, Orc Red, and the leader, Orc White. Since there were limited recognisable colors in his paint set (Warhammer basic paint set thing), he would put 2 dots on some bases, or 3 or 4 or 1 dot. So there could be Orc Red, and Orc 2 red. He never attached mini to base, so he could use the same set of bases for every encounter.
Which brought up another issue, because the bases seemed to transfer luck over, regardless of the mini that was stuck onto it in that given fight. 2 Red Dots always gave my characters trouble. The NPCs attached to it always seemed to roll 20s. Freaking 2 red dot base.