It sounds like what you need is some sort of transaction support so that deletes and adds only happen if both succeed.
It's not a difficult feature to implemented (in fact if I recall there is a pull request open for this feature in beanstalkd) and IMHO would open up a lot of interesting use cases.