This issue is not a bug.

If you have the requirement to correlate on a variable which is not a processInstanceVariable, use the following approach:

1. Map the variable into the intermediateCatch event or the receiveTask:

<intermediateCatchEvent id="paymentEvt" >
    <messageEventDefinition messageRef="..." />
    <camunda:inputOutput>
      <camunda:inputParameter name="localVarName">${varName}</camunda:inputParameter>
    </camunda:inputOutput>
</intermediateCatchEvent>

(Execution Listener with

execution.setVariableLocal()

would work es well)

2. Search and trigger the execution

Execution e = runtimeService.createExecutionQuery()
    .messageEventSubscriptionName(messageName)
    .variableValueEquals("localVarName", varValue)
    .singleResult();

if(null != e)
{
    runtimeService.messageEventReceived(messageName, e.getId());
}
else
{
  // ...
}

—

WARNING: do not copy pase the code below.

For the basic problem see http://jira.codehaus.org/browse/ACT-1106.

Now I encountered a problem which is not that easy solvable by a workaround. Consider the process model attached where we have a "MessageReceiveEvent" within a MultipleInstance sub process. The correlation id is a process variable - local to the token (because of the multiple instance).

Now I would like to do
Execution execution = runtimeService.createExecutionQuery().messageEventSubscriptionName("MESSAGE_NAME").variableValueEquals("correlationVariableName", 777).singleResult();

That does not deliver any results. Instead I have to do something like this:

Execution parentExecution = runtimeService.createExecutionQuery().variableValueEquals(ProcessVariableAdapter.ANFORDERUNG_CORRELATION_ID, anforderungId).singleResult();

WARNING: this line will fetch every execution having a subscription to the "LIEFERANTEN_ANTWORT" message. If there are thousands or houndred thousands of such executions it can make your application go out of memory.
List<Execution> possibleExecutions = runtimeService.createExecutionQuery().messageEventSubscriptionName("LIEFERANTEN_ANTWORT").list();
Execution execution = null;

for (Execution e : possibleExecutions) {
if (((ExecutionEntity)e).getParentId() == parentExecution.getId())

}