Best way to migrate a menu

Hi guys

I have a test site with a huge menu.
The database is a complete mess on this test site and I am building the site again (without dumping the db) into a fresh db..

I can't seem to find any plugin designed for migrating a menu other than this one:

Does anyone have any alternatives or suggestions?
I can't grab the menu directly from the db so I guess I need to be using a plugin.