Yes, in an initially perfect vacuum an object would lose heat. Even if none of the atoms came loose from the object, electromagnetic radiation would be emitted. If the vacuum had some sealed reflecting walls, equilibrium would be reached when the radiation coming back in to the object just balanced that leaving the object.
You can think of the vacuum as an object that can hold energy (the radiation) and thus can have a temperature. As heat flows into it, that radiation temperature goes up.
In the long run, the atoms also will reach thermal equilibrium, as some of them evaporate into the vacuum.
Incidentally, the first law of thermo says that energy is conserved. I think you’re thinking of the second law, which says that entropy always increases. One implication is that heat flows from hot regions to cold ones.
(published on 10/22/2007)