After playing around for a while, I noticed that the issue really only occurs with one specific user account. When I directly assigned the task to this account everything worked just fine. After that, the xPath option worked as well. It really looks like if something is being synchronized into the LC database when a user account has it's first contact with a workflow. If that step could be completed the issue never occurs again - which sounds pretty much in line with what Yog said.
The only difference with the "erroneous" user account seems to be that the family name contains a whitespace - I have no idea if this is relevant.
I'm not able to apply the service pack immediately for some reason, but we'll soon be able to see if that fixes the issue.