I occasionally have Endermen teleport into my mines, creating the possibility that they may move a block of dirt or gravel and inadvertently open up holes for monsters to spill through, ruining the relative safety of my dig sites. As such, I have taken to sealing my mine walls by removing dirt and gravel and replacing it with spare cobblestone.
Unfortunately, I happened to notice an Enderman in what I thought was a dirt-and-gravel-free mine branch wandering around with a block of dirt. Either I failed to replace some dirt (which he subsequently moved) or he picked it up somewhere else and teleported in with it.
Is the second explanation possible? Can Endermen teleport while carrying a block?