One of my users on NW2010 Build 3110 (a few releases behind, sigh) complained that conditional start doesn't work the way defined in the Workflow Designer. In ULS I can see that one of the fields (a lookup) that was not part of the condition didn't have a value and it caused the "Field ... cannot be found on item. Condition will evaluate to false" evaluation result. With this lookup specified, the conditional start works.

What could cause such behavior? Is it a bug fixed in more recent releases?