There are a number of different things that could be causing the packet loss. Being the fact that this is a connectionless (UDP/ICMP versus TCP) protocol going over the internet, you must be willing to endure a certain level of packet loss.

ICMP is a great tool to use when troubleshooting IPSEC tunnels. To determine what is causing the packet-loss, here is one idea to consider to troubleshoot where the packet loss is:

1.) Configure a host-to-host cryptomap containing only a single host on one end with the destination being a single host on the remote end.

2.) Ensure that the 'encaps' and 'decaps' for the relevant Phase-2 tunnel on either end indicate zero for the host-to-host tunnel. You can clear these counters via 'clear cry ipsec sa counters'. You will need to clear these counters on both ends of the tunnel.

3.) Ping from A-to-B for the first part of this test - we'll repeat this later from B-to-A. Set the pings up for 10,000 packets and, for the sake of time for completing the test, a timeout of 0 seconds. Extended pings from a Cisco Router works quite well.

4.) After the pings have completed, gather the output of 'show cry ipsec sa peer | include caps|peer|ident'. This will give you a condensed view of the critical counters for this test - along with the endpoints. From the sending end, encaps imply the outbound Ping Requests sent and decaps imply the outbound Ping Replies Received. As ICMP packets are significantly small, these should equal one-to-one on each end. You may see a number of Ping Requests lost in transit from A-to-B and possibly a number of packets lost in the Reply from B-to-A.

When comparing these counters, if the packets are indeed being lost on the Internet, unfortunately you will not be able to do anything to correct that. If you have access to any upstream routers, you can monitor host-to-host access-list counters to determine where other packet losses are happening - if found, confirm speed/duplex and link saturation to determine why.

Best of luck in your troulbeshooting.