This can be done in Regedit
Open Regedit (Windows Key + R >> and then type in regedit >> Enter
Navigate to HKEY_CURRENT_USER\Software\Microsoft\Terminal Server Client\Default
Then you can delete the entries starting with MRU and followed by a number.
The above registry will only store the 10 most recent unique connections, so navigating to HKEY_CURRENT_USER\Software\Microsoft\Terminal Server Client\Server and deleting all the folders under Server will fully clear the history.
You may not be able to remove the last typed in location, it wont be in the list but it will be in the Computer: text field.
You could also use this FixtIt tool from Microsoft: