I don't really like using "Link Exchange Request" - that is what all the automated ones I get have in the subject.
Here is what I do:
1. When you visit a site you want a link on, there are 4 things you need to do quickly:
1. Find their name
2. Find their contact information
3. Find the page you want your link on
4. Find a page to comment on to make it personal
You want this done in 90 seconds. If you can't find any way to contact them - by form or by email, then move on.
Try to find the webmaster's name on the site. I do a quick check through their pages to see if I can find their name. If I can, I go to #2. If I cannot find their name, then if the link is valuable I try a whois lookup. If the link is only moderately valuable I just write the email without a name.
You also want to find the page you want your link on so you can ask for a link on a specific page.
Lastly, you want to find a page of content that you can comment on.
The key to link exchanges is to keep moving and not get bogged down in the little details. You need to make an email as personal as possible as quickly as possible. I will not spend 10 minutes on one site. Try to keep your time on the site under 90 seconds.
2. If I have their name, the subject will look something like this: John, about your site, domain.com
Don't put www or http:/www. in front of their domain. It looks too much like a generated email.
If I don't have a name, I do not put the domain in the subject line. It looks too automated. The subjects I use then are something like: "comment about your site" "your site" and "feedback on your site"
3. The body of the email should be very quick and to the point. The first line should complement them on their site. It is very important to make sure that it is not generic. Say something about a specific internal page and include the URL to the internal page.
Here is an example of an opening line:
I was looking at your www.domain.com/widgets.htm page and saw that you offered some great widgets. Thanks for all the information on them.
The next part of the body should be a simple link request. Here is an example:
I was wondering if you would be willing to add my site, http:/www.domain.com to your page at http:/www.domain.com/the-page-you-want-your-link-on.html
I think my site would be a quality resource for your visitors. Here is some link text you can use:
Description: Information on purchasing widgets.
You should also include the HTML code for creating the above link to make it as easy as possible for them.
Finally, you want to close your message. You should include an offer to reciprocate if you are seeking reciprocals, if not, the above part works well.
Here is an example closing with an offer to reciprocate:
John, thanks for taking the time to read this. If you would like a link on my site feel free to send me your link text and I'll get yours up immediately.
One thing you do not want to do is put their link up before emailing them. If they see that their link is already on your site, they will be much more likely to not respond to your email. They figure that there is a good chance you won't take their link off.
Instead, you should state that you will get their link up quickly (you need to emphasize that you will get the link up fast) with it being understood that the condition for them getting a link on your site is for you to first get a link on theirs.
Also, don't include any nonsense about how getting more links will improve their Google PR or rankings. They either already are aware of it and don't need you to explain it to them, or they don't care and will swap because you wrote them a nice personal note.
If you have a quality site you will get some good response following the format above. And let's not kid ourselves - PR of your pages matters - if your links pages have a PR 4 or better you will get very good response.