This is the expected behavior for the REST API. As you mentioned, the SOAP API would be the workaround here. If it is known lead, you can query by cookie id using the REST API:
I was under the impression that Marketo is dedicated to REST API for the future, http://developers.marketo.com/blog/marketo-rest-vs-soap-apis-faq/, So I was trying to update our integration code from SOAP to REST, but this so called, 'expected behavior' is almost a deal breaker.
Even the suggestion to use SOAP along side REST as a workaround seems pretty irresponsible to me. SOAP API allows the developer being able to update the anonymous lead's fields even it's not associated as a known one yet, but REST just doesn't allow to do the same task since you can't search it by _mkto_tkr cookie. I'm wondering whether this limitation is what exactly Marketo developer wants ... If that's the case, just being honest in the API documentation would be better.
In my humble opinion, it's a BUG, not an EXPECTED BEHAVIOR.