This 100% tells me enc domains are NOT matching, so please confirm it again and ask them to verify their Cisco side for YOUR enc domain to make sure it is correct.
Andy
[Expert@checkpointfw01:0]# fw ctl zdebug + drop | grep 172.20.138.198
@;1274658776.23010;[kern];[tid_16];[SIM4];sim (vpn_encrypt): drop due vpn_ipsec_encrypt returns PKT_DROP(3), conn: <10.10.20.121,50629,172.20.138.198,80,6>;
@;1274658776.23011;[kern];[tid_16];[SIM4];handle_vpn_encryption: ipsec_encrypt failed: failed to find SA. Dropping packet... conn: <10.10.20.121,50629,172.20.138.198,80,6>;
@;1274658776.23012;[kern];[tid_16];[SIM4];sim_pkt_send_drop_notification: (0,0) received drop, reason: Encryption Failed (5), conn: <10.10.20.121,50629,172.20.138.198,80,6>;
@;1274658776.23013;[kern];[tid_16];[SIM4];sim_pkt_send_drop_notification: sending packet dropped notification drop mode: 0 debug mode: 1 send as is: 0 track_lvl: -1, conn: <10.10.20.121,50629,172.20.138.198,80,6>;