Another excellent point! A correct implementation of proof of work means that we can hand off some (relatively) cheaply generated cookie and then maintain no state in relation to that while the answer is being calculated on the other end.
This stateless principle is implemented in TCP SYN cookies for warding off SYN flood attacks, for instance.
Thank you, also.