We also have a larger number of anonymous leads.
We have done the type of tagging campaign Kimi suggests--keep in mind that this will not address the vast majority of your anonymous leads--this is a way to match anonymous behavior with a known email address. Say you have 100,000 email records and 200,000 anonymous records. Based on email clicks and form fills, maybe 60,000 of your email addresses are already tagged, and 40,000 are untagged. That means a tagging campagin with 100% successful results will only tag only 40,000 leads, still leaving you with 160,000 anonymous leads. And if your experiences are like mine, you're not going to get 100% results.
In our experience, an "update the database" campaign doesn't perform well. I think the atttitude from a lot of people is "You don't know me? Good! I'm protecting my privacy!"
What really worked in our tagging campaigns was to offer a high-quality piece of content, made available without form. Offer a white paper, higlight that its a direct download with no form required, and every click in the email tags the lead to the anonymous record.
You need a completely separate strategy to capture the true anonymous visitors--leads that are being tracked in Marketo, but you don't have an email address on file. There is no easy asnwer--you have to work really hard to create opt-in forms, ideally on every page of your website--and create the forms using Marketo's approach for using a Marketo form on a non-marketo page:
https://community.marketo.com/MarketoArticle?id=kA050000000KyqgCACOne of the best articles I've read on the general philosophy behind opt-in forms and on-page conversions is from Chicago-based web developer Andy Crestodina--he outlines the tips he used to obtain an 19X increase in conversions:
http://www.orbitmedia.com/blog/email-signup-forms