That Lead Status is a Custom field added to your Contact Record.
You can get the list of the Contact Custom Fields by going here "Admin - Settings - Application Settings - General - Custom Fields".
Otherwise, you can query the API "DataFormField" table for this. Make sure the FormId is "-1".
API Table searching is for individual tables. You will have to do several queries for this to work.
What you can do is to do a query say on the "Contact" table first, and collect the Contact IDs.
Then you pass an array of the Contact ID numbers into the Data Query parameter for the ContactAction table.
$contact_ids = array(1,3,5,6,7);
....(QUERY)... array("ContactAction", 1000, 0, array("ContactId" => $contact_ids), array("Id", "ActionDescription"))
If you have 100k Contacts, then you will only need 200 API Calls here.