It's been nearly a year since I did this myself. I believe it's safe to say, users have to be imported first, then the forums, then the topics and then the messages. As you have indicated as well.
I went from DragonFly CMS (php) to DotNetNuke w/YetAnotherForum. I mention that because, well, I guess it doesn't matter, but I exported everything into Excel documents. It was about 2,000 users with I think 160,000 messages.
I exported my Users, Forums, Topics and Messages into their own Excel documents.
If you're not using DotNetNuke, this first link will be of no use to you. This tool here
imported my Users from Excel into my database, then I used the DNN to YAF UserImporter to create the DNN users into YAF.
is two applications I threw together to import my MySQL messages into YAF.
YAF-AddMessages imports the topics/messages from an Excel file into your database.
YAF-Maintenance to sync up forum categories, topics, and whatever else you find in there.
These tools are very ad-hoc and are not a final product for anyone not using the same structure as myself, however, I believe this is a very solid first step in your goal. The code will need modifying to meet your needs of course. It is C# and it's in VS2010.
I think the most fun I had was actually doing the data migration from the old site to the new site, lol.