Was a comment, but moved as an answer:
The latest version of the server (as of minecraft 1.3_01) is using the new region save system. This method means that the server is much more efficient as sending chunk updates to players.
It only happens for us on our lan with slower computers running.
It may be that the client's handler that receives chunk updates is getting flooded, so never gets around to sending the destroyed block event back to the server. The client spends so much time recieving, that it either throws the update away, or the server flags it as "stale" went it is finally gets there (and ignored).
The server notices that the block really isn't destroyed, so once it gets around to it, it sends a chunk update to the client that lets it know the block really exists from the server's perspective (so it pops back into existence from the clients point of view).
Rejoining the game, or hitting [alt] (which pauses the rendering, so the game has more time to receive), allows the client to catch up. The best cure is to make sure that you stand still just after spawning, at least until all the chunks are loaded on the client. You have to ensure that subsequent chunks aren't bombarded all at once, so using server mods like MyWarps or Worldedit's jumpto can cause the issue.
It is especially bad if a virus-scanner kicks in on the slow client machine, causing the client to repeatedly lag behind even with the smaller amount of chunk updates.
This may have been a problem all along, but because the old files took so long to load, they never swamped the client. The rarity of the problem is easy to explain if minecraft is running on a server/client queuing system.