What firmware version is the MX appliance currently running?
Are the affected devices/users under a specific group policy? If so, could you confirm the policy assignments and any custom URL or wildcard entries?
Have you tried any specific domain tests (e.g., blocking example.com) without wildcards? If so, what were the results?
It is likely you would need to contact Meraki Support.