Assuming this is not a Pix config problem:
Are you sure you own the addresses? In other words, could the ISP be routing replys to these addresses to another customer?
Also, have you checked the DNS settings on the inside boxes that don't work? If they are not set correctly, you wont be able to resolve and browse outbound. Try browsing by IP to test.
You can also try doing a snoop or tcpdump on the outside segment to see if packets are getting through.