Which would make things a lot more complicated - vs. issuing a move command on a job id where the server would be responsible for making sure the atomic move succeeded.

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.