Optional
It looks like the issue is due bug in iOS that completely breaks the Universal Links if it gets served an app association file that's too large according to the following site : https://bencollier.net/2016/03/unable-to-open-links-in-safari-mail-or-messages-on-ios-9-3/
The common thread appears to be people who have the app "Booking.com" installed. Unfortunately just uninstalling Booking.com doesn't fix it but you can fix it by following these instructions :
https://infinitediaries.net/how-to-fix-ios-9-x-safarimail-link-bug/