Some computers cannot access Internet, some can

Hi,

we have suddenly a strange problem. We have an XGS136. 

We have two internal servers that need to be accessed from outside and the DNAT & NAT rules have been created accordingly. All the rules ( dnat, loopback, reflexive ) for the two servers are identical except for the destination host, of course. Both servers are working fine and the required services can be reached from outside the firewall and inside.

Strangely one of the servers cannot access the internet. The other can access the internet.

Also, some of the client computers ( all are on DHCP and getting their IP addresses from the firewall DHCP server ) can access the Internet, others can not. I cannot see a pattern.

All of this was working normally until suddently a week ago this problem started.

For both servers I can see in the log files:

access denied - could not associate packet to any connection

When I run a policy test to a website for the two servers I get for both servers: