After defining a host to host IPSec connection, why does the first attempt to connect to it fail?

This is not a bug, but known and accepted behavior for native ipsec in linux 2.6 kernel.

The linux IPSec implementation uses Security Policy (SP) and Security Associations (SA's) to tell it what to do to secure a packet. An administrator defines the SP's and enters them into a database which is stored in kernel memory. SA's are created upon request by racoon, the IPSec userspace daemon....