It's not that difficult, really - the laws of thermodynamics have nothing against directing
your thermal emissions. You could always pack your thermal load in a beam or stream that you point away from the enemy, thus presenting an almost absolutely cold face towards him.
Of course, you can also store your emissions aboard, in a sink of some sort, for the duration of the stealth mission. You then dump the "hot potato" when convenient, or even use it as a weapon!
As for the use of paint, one might argue that Kirk's original "starship grey" would be a good compromise between low albedo (for avoiding being seen because of reflected light) and low absorption (for avoiding being seen because of collected and radiated heat). Anything lighter, and local sunlight would reveal you; anything darker, and you become a sponge of energy that you then radiate in the infrared range.