Go to:
1. Settings
2. Applications
3. Manage Applications
4. Select Filter
5. Select All
6. Select "Maps" application. It will show the following
Total xxx MB
Application XXX MB
Data xxxMB if it is other than 0 this is your recent destinations
7. To clear recent destinations, select "clear data" button.
