Two of the housecarls, Gregor and Valdimar, are constantly wandering around Skyrim and don't sleep on the premises.

Any way to fix that (PC) ?

Try the http://skyrim.nexusmods.com/mods/25127. I'm pretty sure it fixes Valdimar; I'm not certain whether it fixes Gregor or not, though.