Hi Gim,
you have already listed two main reasons for it not to work: DNS resolution on the GW or FW policy in place that does not allow such connectivity. There might also be the third reason: the client itself goes via third party proxy and does not cross your FW in question.
I would suggest to start with two first assumptions.
1. Check DNS resolution for the specific FQDN is working of the FW enforcement point.
2. with curl, try to open URL in question directly from FW
3. If both 1 and 2 are working for you, start looking into connectivity and policy issues between the Web client and FW. You can use "fw monitor" to do so
I hope this helps. Please let me know how it goes.