They can move any block (even bedrock) and including player-placed blocks according to the forums. It's annoying a LOT of people, not just due to the vandalism on their structures - after a few weeks in the game the landscape is ruined from Endermen taking random blocks at night.
An irritaing aspect is that when they die, the block they're holding is destroyed, so if they've picked up one of your diamond blocks then the sun comes out in the morning - poof!
I think they should move blocks instead of actually steal them (so drop the block when they die) and also make it less random - have them actually build something, even if it's just a random collection of blocks all in one place.