My understanding--not a lawyer--is that the rights to the letters belong either to their creators or to the website to which they were submitted, depending on what the website's fine print says. (For instance, questions and answers at a lot of Q&A websites become the property of the website, and they can share them, publish them, use them in ads, etc.)
So the first thing you need to do is read the fine print at the place you're finding them.
In all honesty, this sounds like a rights nightmare. I'd create my own love letters, using the real ones only as inspiration.
Maryn, doubting you can contact all the people who wrote them, if you need to