It looks like Check Point's only categorization for this site is "Computers / Internet". Are users attempting to access it by directly entering in that URL? Or are they searching for it and clicking on a search result?
One side effect I've seen from blocking the "Web-Advertisement" category is that many of the "top" links on Google (which are actually Ad hits) will not work.
If they are going directly to the URL, it could be that some portion of the site is redirecting to some ad or click-tracker before going to the actual webpage. If that is happening, there may not be much you can do besides white-listing "ad-balancer.at". Which I'm sure you don't want to do, but a poorly engineered website may not leave you a choice.
R80 CCSA / CCSE