Hello Norman, unfortunately there’s no other option how to clear the recipients history, the recipients are only saved in the above mentioned cache which you can clear from the application settings, all other contacts displayed by auto-complete while composing a new message are fetched from your Contacts folder.
Only other case would be a Global Address Book, which is usually located on your mail server and is shared for all users on domain, if however you’re using a public Gmail account, you don’t have this feature available, thus my best suggestion would be clearing your Contacts folder.
Regards,