The best answer I have would be start with the Discussion object, for example via the API, you would use the contents service, such as with this discussion:
then, you would use the Messages Service that is exposed in the "resources" section of the above call under "messages":
From there you should get all the messages for a given thread, you will be able to stitch together the tree using the parent attribute, but shouldn't need to go all recursive style.
Similarly, you would use the "attachments" resources to grab all related resources. etc.. etc...
It sounds like you are going down the right path, but wanted to lay out some of the details to make sure we were talking apples-apples.
Hope this helps. =)
Thank you Ryan,
It's nice to see that I will not need to go recursive style on my export.
I'll try this today.
It definitively helps