In the middle of the day, I assumed that I'd lit up all my houses, but then I heard night-mobs including the Endermen. There are a lot of caves under my little village, so I thought that they must be in the caves. But, I don't recall Endermen ever going into caves.
Yes, Endermen can spawn underground as long as they have enough clearance (3 blocks vertically) and the light level is low enough (7 or lower).
One thing to keep in mind is that during a rainstorm, Endermen will teleport randomly if they're on the surface: if a cave or indoor dwelling happens to be within their teleport radius, there's a chance you'll find them there, Endermanning it up.
2Additionally, they can sometimes touch flowing water while wandering aimlessly and that will also make them teleport (even if it is not raining or they are sheltered from rain in the caves). They will teleport on random place disregarding the light level there, so you can sometimes find them in fully lit and safe homes. This happens rarely enough to not cause problems.– KcatsJun 1, 2012 at 6:03