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.