When a lead first visits a page on a domain, a new anonymous lead record is created in Marketo. The ID of the this record is based on the Munchkin cookie (ex. id:561–HYG–937&token:_mch–marketo.com–1374552656411–90718).
When certain conditions are met the anonymous lead is associated with a know lead and the user will have a queryable marketo ID (ex. 42065).
However, there are situations where the lead has a marketo ID (because he clicked the link in the email) and an api request to (rest/v1/lead/42065) returns an empty result  array.
Why is that?
Anonymous Lead Promotion to Known Lead – Munchkin V2 Behavior