I think it might be ligitimate request.
If you go and check their site using domain tools you will se that they have reached SEO score of 90%. This indicates that they would like their site to be placed on top of serch results. And to achieve this on google search engine you need to make sure that your site is not linking to to many other non relavant sites and that not to many other non relavant sites link to yours. Wheter the site is relavant or not is determined by the site contents and from where do most uses come to that site.

Anywhay if you do decide to reply to them I still recomend using some caution. Use PGD mail so you don't expose your personal E-Mail adress to them in case they are connected to some spammers.
You can tell them that link to their site was in some user profile which was created by a spam bot. And becouse user profile was deleted recently it will take google some time to notice that there is no longer such link on our site.