I short, there is nothing you can do. It's something everybody has to live with. Verifying that an email address is reachable (--> click a confirm link) is what is usually done, but it is little effective.
A lot of people use throwaway email addresses because they think there is no good reason why you should know one of their mail addresses, but there are good reasons why you shouldn't know any of them (in fact, I just checked and saw that much to my surprise, I used a valid email address to register on Gamedev... this is a rare thing).
Databases growing is -- usually -- not that much of an issue. While storage is not infinite, it is still affordable. A million or two user profiles will still conveniently fit on one disk, no hassle (ten million will, too... and if you have ten million accounts, you can afford a second disk). Lookup time does not go up that significantly either, and if it did, it would not matter (login is not that time critical).
Most games choose to never delete an inactive account, even if it hasn't been used for years, unless it's one that has never been used (or never gained a level). Why? Well because it costs next to nothing to keep it, but if you delete the wrong account only a single time, the shit storm that will come will be huge as soon as that user tries to log in again after 3 years.
Do you set a limit in the server to prevent too many clients.
Setting limits account/character numbers is unadvisable. A per-account limit of characters means people will create more accounts. A per-server limit on accounts means you have created a by-design DoS method (which inevitably someone will exploit).
How do you even know whats a legitimate account is, if they fill in all the account fields with uneque values for the account data.
Depending on your business model, one valid way may be: Anyone who paid you is "valid". However, again, depending on your business model, it may not be easy or applicable. If you are purely ad-driven, for example, how do you define "getting paid"? Impressions? Clicks? Conversions? Any of these might pay you or might prospectively get you paid.
Possible candidates for "non-legitimate" accounts would be ones that exist for years and have not gained one level in that time. But of course it's a tough call (you might still delete the wrong account!), and as soon as you publish a rationale, cheaters will make sure their mules all have e.g. level 5 so they will not be deleted.