Email customers who have shopped more than once?

I've been thinking about giving my recurring customers some benefits, but in order to do so I need to know who they are... And in a perfect world, I'd only be getting those who actually have subscribed aswell, as Norwegian law is fairly strict on that matter.

So, any ideas, except for going through them manually, one by one, and make a mailinglist?

Use the Email Address Exporter addon to extract the email addresses.
Or you can use the built-in Newsletter Manager to do direct sending.

Both of those use the built-in query_builder support which selects certain audiences based on a predefined list of criteria. If you want to add new options to the list, you'll need to write the correct SQL database extraction code and manually add it to the query_builder table. There are some forum discussions on the topic, but you'll likely find one of the existing options already handles what you're asking for, or closely.