My situation is pretty unique, so I don't know if it'll be helpful to anyone else, but here's what I've done so far:
1. I have a Google apps account through my work, setup to show up as exchange on my iPhone.
2. I have the Google apps sync tool on my PC, which syncs my outlook contacts to my Google account.
3. I cannot install the iCloud sync tool because I have Windows XP (still the most common business OS, so until my clients stop using it...), and the sync tool requires Vista, 7 or 2008. I do have a test server I run 2008 on, so I synced that installation of outlook (hey, it's not a real server) to my iCloud account, then exported the contacts to CSV, copied that over to my PC and imported to outlook.
My Outlook contacts auto-synced to Google, and from there into my Exchange account on my iPhone within a minute. Now everyone is on my iPhone finally, under my Exchange account. I then used Google's "find & merge duplicates" tool to do just that, so everything is beautiful. As long as I never change jobs and give up this email address, of course.
You should now be able to take that master list and import it directly to iCloud via iCloud.com.