Many forums in the world use a threaded message structure. In this structure users can decide to which message in a thread they want to reply. You can walk down a specific message tree within a thread. Some other forums, like WW for example, use a flat structure where it is only possible to add a message to the end of the thread.
Personally I like the flat format because it is cleaner and easier to read, but because there are also forums using some threaded structure that I am not sure if those users would feel less comfortable in a flat environment.
Flat all the way! In addition to the advantages you cite, it makes people do a little extra work to fit their contributions into the flow. And that's a Good Thing. Also, disable automatic quoting. Another thing that contributes to the ease of use of WW.