If you keep them in linked plaintext then they will get harvested sooner or later, you can improve your odds a little by protecting clickable email addresses using e-mail entity encoding (google for it) so that it makes it harder for them to find addresses on the page.
I'd also suggest encoding parts of the "mailto:" prefix so that this doesn't become the weak part of the system...
Otherwise your best bet is to not show email addresses unless the user registers or deal with it the FriendsReunited does and don't actually expose the email addresses on the site but instead act as a trusted 3rd party which establishes communication between the two people.
If the purpose of the email addresses is to provide users a way to contact each other you could use a simple contact form. I had a similar situation and did this.
I made a clickable link to a contact form and passed a var that represents the targeted user. I don't let the user fill in a 'To:' so the form is useless to anyone that might try to utilize it as an open emailer. When the form is submitted the form handler does a lookup using the var I passed for the actual email address. It formats the email and sends it on.
lorax: I've a form, but still need a visible address, it's involved with trust in our service: only 0.05% use the form, they prefer own contact methods. I think a good part will leave if I cut options.