If you're comfortable using regedit go to:
HKCU \ SOFTWARE \ MICROSOFT \ WINDOWS MAIL
The tree will open and you'll see an entry for Recently Used Addresses. Click this and on the right side pane you'll see a list. Select All in this list and delete. This will delete ALL autocomplete entries but lets you start again, still using it.
NOTE: Right click on the Recently Used Addresses folder in regedit and EXPORT first. In case you have a problem you can restore it.
I just tried this and it works for me.