Verify deletes in backup restore test

Using the new function to detect when tombstones are really, really gone
so the test is more reliable.
Also, a bit of refactoring of the delete verification and wait_until
functions to make it cleaner.