Summary/tl;dr - Riak 1.0.0 has introduced more control over deletion with the delete_mode setting.
If you plan to delete and recreate objects under the same key rapidly, and there is enough disk available to store tombstones, it is safest to set delete_mode to keep.
The default three second delay for removing tombstones balances keeping the tombstone around long enough for any rapid delete/recreates, but unlike the keep mode it does remove the data.
Riak keeps your objects available during failures by storing multiple copies of the data. This redundancy makes deletion more complex than a single node database. For example, Riak needs to ensure deletes issued while nodes are down get applied when the nodes recover, or resolve what happens if the network is partitioned and an object is deleted on one side but updated on the other side.
Deletes in Riak are a two step process, first it writes a tombstone objects to the N replicas and only once all replicas have stored the tombstone are they remove