I reguarly receive emails like this: Are they scams? Or can it be of benefit to swap links? PR for the blog they are asking about is PR0.
I have never received a message from NoMoreEmails, but I'd suggest checking their website and seeing if they have a large number of ads up for sites similar to yours.
I checked their two sites they will put my link on and there are no ads and only a couple of linkson their link page. The site they want me to link to is a job site which looks like any other job site. I checked their page rank and they are valid. I might give them a try. Just a bit cynical as I have a PR0 blog and they are offering me two links on higher sites for my one link on mine.
This is probably a real link exchange and the person is using a link exchange program that is automated. Maybe that is why you got such a formal-looking email.
This is the standard link exchange template included in IBP&Arelis so they're most likely valid link requests, but simply sent in bulk by a program.
Here's the deal. They will offer a nice friendly link exchange. You both get a virtually worthless reciprocal link. A few weeks later, once you have forgotten about it, they simply remove your link. They get a free one way backlink, you get nothing. Oldest trick in the book.