My guess is that this other assembly isn't loaded before WF is trying to deserialize. You can test this by simply new-ing up an instance of this type before your application starts executing (i.e., in the Main method of your Program class, for a winforms app).
If this is a case, you can try a few things.
First, force loading of all assemblies you need in memory before deserialization (like the test above). This method, imho, sucks.
Second, you can add logic to runtime type resolution. It appears to be possible, but I've never done it.
Third, modify your serialized workflow to give it the information you need to load the type.
I'm not sure how you are serializing your workflow, so I can't tell you exactly how to do this. I can tell you that workflows are serialized to xaml. The XamlReader can, on deserialization, load assemblies of types included in the xaml. This is done by using a special type of XML namespace.
Let's say this is your missing type (in a serialized workflow):
<MyType><!--blahblah--></MyType>
and MyType is defined, in the assembly MyCode.DLL:
namespace MyCodeNamespace
{
public class MyType { /*yadda*/ }
}
then the namespace for this type would be: clr-namespace:MyCodeNamespace;assembly=MyCode
and it would appear in your serialized workflow as:
<MyType namespace="clr-namespace:MyCodeNamespace;assembly=MyCode"><!--blahblah--></MyType>
The XamlReader recognizes that namespace, determines the assembly is called MyCode.DLL or MyCode.EXE, looks for it, loads it in memory, and looks for MyCodeNamespace.MyType.
The question then becomes, "how do I get my workflow to serialize that namespace???" The answer is "I dunno". Perhaps you can use the following assembly attributes:
[assembly: XmlnsPrefix("clr-namespace:MyCodeNamespace;assembly=MyCode", "MyCode")]
[assembly: XmlnsDefinition("clr-namespace:MyCodeNamespace;assembly=MyCode", "MyCodeNamespace")]
but I'm not sure if the Workflow serializer will respect these. Hell, I'm not even sure if the Workflow serializer will respect the clr-namespace in the first place. You can try it out, and if not ask another question on SO based on this.