Maybe it is a little creepy... (not if they don't find out though!)
One thingy you could do is send a gift to their email address - either through PayPal, or a voucher for a popular online store. If you really want to mail something, maybe you could offer them an incentive for giving their mail address when they sign up. Even tell the truth: "Top affiliates will receive a personal gift in the mail, all you need is to fill in your address" etc

Best of luck,

Felix