At least in the case of SimpleDB, replaying requests is usually not a problem -- if you Put or Delete an attribute which has already been Put or Deleted, it has no effect.
An attacker monitoring the deletion can with impunity wipe out your data at a later date.
Only within the next 15 minutes. Beyond that point, AWS will reject the request for having excess clock skew.
As for "wonderful heisenbugs" -- the AWS services return a clear "hey, your clock is broken" error, so it wouldn't be very hard to developers to figure out what was going on.