My issue with this was because I had the contact info tab set to permission level higher than that of the rest of the site.

If the available searchable fields are in any way not searchable to a given permission level, such as the tab they are located within, the link simply doesnt appear.