After I realized that I was not going to go anywhere with actually solving the problem, I thought it'd be more interesting to make a purely functional implementation of the VM and compare the performance with the mutable solution.
In order to refactor to a functional solution, all mutable state needs to be replaced with items that return a new instance of the code. This means that now we can write the main "loop" as a standard functional construct, reduce, which applies the list of operations to the VM and creates a new instance each time.
Adjusting the code to a functional style was a small transformation. Each instance of
swap! was replaced with a creation operation instead. No more dereferences (@) signs cluttering up the code, and something that is much clearer to understand.
So how does this affect performance? Previously, the code did 1000 iterations in 3.85 seconds. Running the functional code gives almost exactly the same results (1000 iterations in about 3.75 seconds). I'm not sure how this compares to other implementations of the same code (I suspect poorly!), so I'll hunt around for some comparisons. Either way, I will definitely prefer no mutation wherever possible...
I thoroughly enjoyed the ICFP contest this year. Learnt some bit-fu, a small amount of orbital mechanics and actually managed to make some progress even though ultimately I didn't even submit a single solution :)