I have done several WF4 projects so lets see if I can add any useful info to the other answers.
From the description of your business problem it sounds like WF4 is a good match, so no problems there.
Regarding your concerns you are right. Basically WF4 is a new product and is lacking some important features and has some rough edges. There is a learning curve, you do have to do some things differently. The main point is long running and serialization, which is something the average developer is not used to and requires some thought to get right as I hear far too often that people have problems serializing an entities framework data context.
Most of the time using workflow services hosted in IIS/WAS is the best route when doing these long running type of workflows. That makes solving the versioning problem not to hard either, just have the first message return the workflow version and make that a part of each subsequent message. Next put the WCF router in between that routes the message to the correct endpoint based on the version. The basic is never to change an existing workflow, always create a new one.
So what is my advise to you?
Don’t take a big gamble on a unknown, and for you unproven, piece of technology. Do a small, non critical, piece of the application using WF4. That way if it works you can expand on it but if it fails you can rip it out and replace it with more traditional .NET code. That way you get real experience with WF4 instead of having to base a decision on second hand information and you learn a new and powerful technology in the process. If possible take a course on WF4 as that will save you a lot of time in getting up to speed (shameless self plug here).
About the Simple State Machine. I have not used it but I was under the impression it was for short running, in memory, state machines. One of the main benefits of WF4 is the long running aspects.