Companions (the warrior and rogue storyline companions) don't seem to heal (edit: properly) at taverns.