I was experimenting with Persistance and created some workflow instances and unloaded them. these appeared in my database with appropriate Guid's. I then closed the application and reopened it and returned the State of the workflow fine using:

    StateMachineWorkflowInstance stateMachineWorkflowInstance = new StateMachineWorkflowInstance(workflowRuntime, instanceId);
    state = stateMachineWorkflowInstance.CurrentState.Name;

I closed the application again and then modified the workflow in the designer adding a new state and putting it between the two existing states using SetState activities.
When I compiled and ran the application again and tried to return the State I got the following error:

Index was outside the bounds of the array.
System.Runtime.Serialization.SerializationException was unhandled
  Message="The object with ID 28 implements the IObjectReference interface for which all dependencies cannot be resolved. The likely cause is two instances of IObjectReference that have a mutual dependency on each other."
  Source="mscorlib"
  StackTrace:
       at System.Runtime.Serialization.ObjectManager.GetCompletionInfo(FixupHolder fixup, ObjectHolder& holder, Object& member, Boolean bThrowIfMissing)
       at System.Runtime.Serialization.ObjectManager.CompleteObject(ObjectHolder holder, Boolean bObjectFullyComplete)
       at System.Runtime.Serialization.ObjectManager.DoFixups()
       at System.Runtime.Serialization.Formatters.Binary.ObjectReader.Deserialize(HeaderHandler handler, __BinaryParser serParser, Boolean fCheck, Boolean isCrossAppDomain, IMethodCallMessage methodCallMessage)
       at System.Runtime.Serialization.Formatters.Binary.BinaryFormatter.Deserialize(Stream serializationStream, HeaderHandler handler, Boolean fCheck, Boolean isCrossAppDomain, IMethodCallMessage methodCallMessage)
       at System.Runtime.Serialization.Formatters.Binary.BinaryFormatter.Deserialize(Stream serializationStream)
       at System.Workflow.ComponentModel.Activity.Load(Stream stream, Activity outerActivity, IFormatter formatter)
       at System.Workflow.ComponentModel.Activity.Load(Stream stream, Activity outerActivity)
       at System.Workflow.Runtime.Hosting.WorkflowPersistenceService.RestoreFromDefaultSerializedForm(Byte[] activityBytes, Activity outerActivity)
       at System.Workflow.Runtime.Hosting.SqlWorkflowPersistenceService.LoadWorkflowInstanceState(Guid id)
       at System.Workflow.Runtime.WorkflowRuntime.InitializeExecutor(Guid instanceId, CreationContext context, WorkflowExecutor executor, WorkflowInstance workflowInstance)
       at System.Workflow.Runtime.WorkflowRuntime.Load(Guid key, CreationContext context, WorkflowInstance workflowInstance)
       at System.Workflow.Runtime.WorkflowRuntime.GetWorkflow(Guid instanceId)
       at System.Workflow.Activities.StateMachineWorkflowInstance..ctor(WorkflowRuntime runtime, Guid instanceId)
       at TestApp.WorkFlowEngine.GetState(WorkflowRuntime workflowRuntime, Guid instanceId, String& state) in C:\temp\Technologies\Tracking\SimpleTrackingSample\CS\TestApp\WorkFlowEngine.cs:line 42
       at TestApp.Form1.GetState() in C:\temp\Technologies\Tracking\SimpleTrackingSample\CS\TestApp\Form1.cs:line 122
       at TestApp.Form1.btnLoadWorkflow_Click(Object sender, EventArgs e) in C:\temp\Technologies\Tracking\SimpleTrackingSample\CS\TestApp\Form1.cs:line 81
       at System.Windows.Forms.Control.OnClick(EventArgs e)
       at System.Windows.Forms.Button.OnClick(EventArgs e)
       at System.Windows.Forms.Button.OnMouseUp(MouseEventArgs mevent)
       at System.Windows.Forms.Control.WmMouseUp(Message& m, MouseButtons button, Int32 clicks)
       at System.Windows.Forms.Control.WndProc(Message& m)
       at System.Windows.Forms.ButtonBase.WndProc(Message& m)
       at System.Windows.Forms.Button.WndProc(Message& m)
       at System.Windows.Forms.Control.ControlNativeWindow.OnMessage(Message& m)
       at System.Windows.Forms.Control.ControlNativeWindow.WndProc(Message& m)
       at System.Windows.Forms.NativeWindow.DebuggableCallback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam)
       at System.Windows.Forms.UnsafeNativeMethods.DispatchMessageW(MSG& msg)
       at System.Windows.Forms.Application.ComponentManager.System.Windows.Forms.UnsafeNativeMethods.IMsoComponentManager.FPushMessageLoop(Int32 dwComponentID, Int32 reason, Int32 pvLoopData)
       at System.Windows.Forms.Application.ThreadContext.RunMessageLoopInner(Int32 reason, ApplicationContext context)
       at System.Windows.Forms.Application.ThreadContext.RunMessageLoop(Int32 reason, ApplicationContext context)
       at System.Windows.Forms.Application.Run(Form mainForm)
       at TestApp.Program.Main() in C:\temp\Technologies\Tracking\SimpleTrackingSample\CS\TestApp\Program.cs:line 18
       at System.AppDomain.nExecuteAssembly(Assembly assembly, String[] args)
       at System.AppDomain.ExecuteAssembly(String assemblyFile, Evidence assemblySecurity, String[] args)
       at Microsoft.VisualStudio.HostingProcess.HostProc.RunUsersAssembly()
       at System.Threading.ThreadHelper.ThreadStart_Context(Object state)
       at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
       at System.Threading.ThreadHelper.ThreadStart()

Inspecting the database and looking at the Workflow table showed that there was only one row in there with the WorkflowDefinition column being:

<ns0:Workflow1 InitialStateName="Workflow1InitialState" x:Name="Workflow1" DynamicUpdateCondition="{x:Null}" CompletedStateName="{x:Null}" xmlns="http://schemas.microsoft.com/winfx/2006/xaml/workflow" xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" xmlns:ns0="clr-namespace:Microsoft.Samples.Workflow.SimpleTrackingSample;Assembly=SimpleTrackingSample, Version=3.0.0.0, Culture=neutral, PublicKeyToken=null" />

Obviously it isn't seeing the change made as a different version and existing instances must just reference this Workflow.

What is the procedure for changing a workflow and allowing existing instances to still be loaded from persisted state?

Also, is there a way that the existing instances could take on the changes to the workflow. Obviously this gets extremely compilcated in the fact that if you remove a state from a diagram and the instance is in that state decisions will have to be made on what state it should be in.

I've posted this on the MSDN forums and hopefully someone will point me in the right direction. 

UPDATE 

"If you change the definition of a workflow and recompile it you need to change the assembly version.  The existing instances (unloaded or in memory) need the original version of the type/assembly in order to be deserialized correctly.  If you need to change the definition of an "in-flight" running instance you'll need to use the dynamic update functionality.

Thanks,
Joel West
MSFTE - SDE in WF runtime and hosting"

 Guess I'll need to look into dynamically updating the workflow on the fly and seeing how it handles this.

A few forum posts here: 1 2