The reason this happens, is that the Samsung Keyboard automatically imports your contact information, including all email addresses saved in your synchronized contacts. This list can be quite long, since it might include any address you have ever received and email from or written an email to (compare with your "Other Contacts" in Gmail).
As for now, the only way to fix this, is to revoke Samsung Keyboard's access to your contacts and delete your keyboard data.
Here is how to do it:
Go to Settings > Application > Application manager > More > Show system apps > Samsung keyboard > Permissions > Deselect "Contacts"
Then go back one step and under "Storage" select "Clear Data".
Please note, that this way your personal dictionary also gets deleted. It is however MUCH faster than manually deleting each of the potentially 1000+ email addresses in your dictionary.