I don’t know the answer offhand, but here are some things to look at:
1) When the “no restrictions” rule was added, was it for TCP, UDP, or all IP?
2) When the “no restrictions” rule was added, is there anything in “front” of it?
3) When the auditors make the attempt and fail, what sort of log messages do you see? If you don’t see any, then ask the firewall admins if they would turn on more logging just to test – pretty please!!
4)Is this traffic going through any sort of NAT scheme. Some VPN solutions need to be tweaked to work in a NAT environment.
5) If I recall correctly, the cisco VPN client can be set up to use UDP or TCP for the VPN session – This often deals with trouble getting through firewalls.
Hope that helps,