Daniel
I have been through that loop and here's what you do.
Send a letter to all your clients you don't have email for.
Make the sole reason for the letter a Competition to WIN something.
Make it something worthwhile as a prize. :
and to make admin easy for you, they need to do it by email
Over time and a number of comps (which give you another excuse to stay in touch) you will get emails.
You then start to intersperse email with letters, postcards etc so you can contact more regularly at a cheaper overall cost.
Send them information, how to guides, comps etc as well as sales letters so you don't pss them off too much.