I have a similar system, but instead of a plain passcode, I have a (simple, and probably not very secure) hashing method that I can do in my head.

My message looks like this: <machine> <hashed passcode> <number>

The passcode is "hashed" with the number. When the server receives the message, it adds the number to a deny-list. That way, the number is only good for one use.

Also, the number has to conform to a certain pattern. I might change that to a pre-generated list of valid numbers, but for the moment, I can work out a valid number with pen and paper.

Not perfect, but I think it's good enough.