I found this thread in the apple forums for steps on an iphone/ipod, and it seems to work on the ipad too. The process involves doing a complete backup and restore of your ipad. For me the whole process was about an hour.
- perform a complete backup of your iPad in iTunes
- download and install iBackupBot for iTunes
- launch iBackupBot for iTunes and select the backup that you just completed
- select Plugin / Recent Email Address
- if you're using the trial version you'll need to click Cancel from the next dialog
- in the Recent Email Address Viewer window select all the addresses you want to delete and click "Delete selected note"
- click close
- click Restore backup file to iPhone/iPod touch (it doesn't mention iPad in the current version but it works)