After struggling with this same issue for a couple of days, I have resolved both the mail embedded link issue and the Google search result link issue (at least for me).
I downloaded the following file Iphone7,2_9.2.1_13D20_Restore.ipsw from one of the many sites available - I used a website called ipsw.me
A full backup of my phone was performed via iTunes.
I then connected my iPhone to my macbook (iTunes). While holding down the 'option' key, I selected the Restore iPhone option from the top section referencing the IOS version (stated current version was IOS 9.3)
Holding down the 'option' key allowed me to select the previously downloaded ipsw file.
My phone displayed "Restoring iPhone".
After the phone rebooted, I selected restore as new - yes, its a huge pain. I downloaded all my apps again. Prior to all of this, I made sure my photos had been stored on iCloud, as well as Notes.
I did not restore from a backup - it seems this is the crucial part.
Towards the end of the restore process, my iPhone started downloading the IOS 9.3 update. It is currently downloaded BUT NOT INSTALLED.
I am now 5 hours later, and both links in Google search and embedded links in email are working fine. Sure, I am using IOS 9.2.1 and I don't have the new functionality of IOS 9.3, but this is a small price to pay for having a fully functional phone once again.
I hope this works for you too.......obviously, backup your phone first, store things like photos in iCloud and proceed at your own risk as performing stuff like this can (and has in the past) caused me to lose data.