API search incorrect results

API search incorrect results

Hello, I'm trying to build a small script that would fetch a lead that has not been contacted, and I tried many different search criteria without any luck, here's one of them- 
https://www.zohoapis.eu/crm/v3/Leads/search?criteria=Lead_Status:starts_with:Not&per_page=3

Making this request once returns leads correctly, BUT if I change the lead status to 'Contacted' , same lead gets returned ignoring the search.
Although, after about 2-5 minutes it is no longer returned, not sure if this is caching or what is happening, please enlighten me because it really makes no sense.

Thank you!
Tomas

Attaching a quick video of it in action-
https://screencast-o-matic.com/watch/c0VVq9VwegX


ALSO

Is it possible to use > (more than or less than) operator in the search criteria somehow?