Great discussion, guys! kobuki, I had not heard of the concept of monotonic functions before. With your proposal in the last post to not store state on either end, that could be a very simple solution for sensor nodes that just spit out data, other than the gateway needing to keep track of the value for each node. It seems like it would work for bidirectional communication too, where the gateway initiates a command to the node. The node would just discard the first command after a reboot and then keep track of the gateway's value. However, if you didn't save the gateway's value between reboots, you'd have to power cycle every node after a gateway reboot to reset the counter.
I was coming at the problem thinking about a handshake where neither side needs to keep track of anything between transmissions. It is at the expense of power though, because now instead of one or two packets (data packet and an ACK), we're up to three or four (request key, send key, send data, ACK).
Regarding Arduino's random not being random - in an earlier test I did use randomSeed(analogRead(0)), however I left that out of the library because not everybody will have their analog pin 0 disconnected. That could be added to the sketch during setup if desired. And even then I know the arduino can't generate a true random value, and having only one byte of random key might not be sufficient enough for military grade applications, but for me, it's good enough!