We see a significant increase in this error under high load:
2015.01.20 08:15:02 org.jivesoftware.openfire.handler.IQBindHandler - Error during resource binding. Session not found in [...] for key xmpp.domain.com/3f4dae0a
We can confirm via other log entries that the target session has been created, but it appears there is a race condition in the server that can cause the session to become temporarily invisible in certain cases.
In particular during the authentication handshake, there is a small window of time (not synchronized) where a session has been removed from the pre-authenticated sessions list, but has not yet been added to the core routing table.