Lead ID never changes. However, it is possible that you have multiple records with the same email address and different Lead IDs. Also, if you merge records, only 1 of the Lead IDs will remain. Also, it is possible that something is wrong with the API call that you're making.
In any case, it's probably best to open a support case and provide specifics, such as a specific email address and Lead ID, plus the exact API call request and response. Without that info, it will be impossible to determine the cause of the issue you're experiencing.
Thnx for your response Jeb!
I;m kinda new to Marketo, how do i open a support case?