I'm not a minecraft player, but I'm going to suggest the "obvious" answer:
Obsidian
It's rare to find naturally, it only occurs where water is pouring on to lava. This means naturally occurring instances are usually over a lava pool, so mining them is fun.
You can, however, create your own obsidian by forcing water to pour on to lava, but this will destroy the lava source in the process (and thus, you need 1 lava source to create 1 obsidian block).
It can only be mined with a Diamond pickaxe and takes a whole 15 seconds per block to mine this way. It can be removed with other tools, taking 50 seconds per block, but you won't get the obsidian to build with that way.