One cheap and cheerful way is to look for the second packet in the three-way handshake. It's easy to spot, as unusually it has both SYN and ACK flags set, which is generally unique to a given connection. Although it is still possible for the originator not to respond with the third and final packet, that's entirely by the grace of the originator: at this point, you have indicated that you're willing to have this conversation, and as far as you're concerned, it's established.
I logged those with
iptables -A OUTPUT -p tcp --tcp-flags SYN,ACK SYN,ACK -j LOG --log-prefix "Connection established: "
And you can see it working with eg sshd:
client% telnet 192.168.3.1 22
Trying 192.168.3.1...
Connected to 192.168.3.1.
Escape character is '^]'.
SSH-2.0-OpenSSH_5.3
server% tail -1 /var/log/facility/kern
Feb 18 05:06:29 server kernel: Connection established: IN= OUT=eth0.11 SRC=192.168.3.1 DST=192.168.3.11 LEN=60 TOS=0x00 PREC=0x00 TTL=64 ID=0 DF PROTO=TCP SPT=22 DPT=59292 WINDOW=14480 RES=0x00 ACK SYN URGP=0
One quick note in passing: what you're currently logging is not denied connections, but denied packets; that's not the same thing. But I've assumed that you asked for precisely what you want, and have answered accordingly.