In last few days I have noticed that questions API returns questions that where deleted hours before the API call.
This is a short example, if more logs are need to pin point the problem, please notify me and I can do further debugging of singular API call
I executed these API calls: (Timestamp is CET)
INFO 2016-06-23 22:12:31,020 Calling url: http://api.stackexchange.com/2.2/questions?page=1&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:31,528 Calling url: http://api.stackexchange.com/2.2/questions?page=2&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:32,028 Calling url: http://api.stackexchange.com/2.2/questions?page=3&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:32,529 Calling url: http://api.stackexchange.com/2.2/questions?page=4&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:33,030 Calling url: http://api.stackexchange.com/2.2/questions?page=5&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:33,530 Calling url: http://api.stackexchange.com/2.2/questions?page=6&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:34,041 Calling url: http://api.stackexchange.com/2.2/questions?page=7&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:34,541 Calling url: http://api.stackexchange.com/2.2/questions?page=8&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:35,041 Calling url: http://api.stackexchange.com/2.2/questions?page=9&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:35,542 Calling url: http://api.stackexchange.com/2.2/questions?page=10&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:36,043 Calling url: http://api.stackexchange.com/2.2/questions/25529155;29141729;9713058;2893819;574594;5775866;16236641;9980283;2798376;37984723;3762763;10267367;11679373;24650838;37333723;218384?page=1&pagesize=100&order=desc&sort=creation&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
INFO 2016-06-23 22:12:36,700 Calling url: http://api.stackexchange.com/2.2/questions/37939005;37944196;37956388;37956760;37968709;37837266;37839417;37841709;37930225;37646430;37669678;37694508;37706072;37727485;37735057;37735770;37738472;37743519;37743936;37748375;37749423;37758097;37766674;37767459;37775722;37781973;37782369;37791495;37792853;37798061;37800840;37803288;37809383;37811323;37821848;37976189;37827452;37827997;37828819;37830193;37830288;37832873;37834068;37847045;37847443;37847446;37851954;37854788;37858598;37861209;37862867;37865853;37868442;37869913;37872327;37872608;37873267;37873748;37874105;37874997;37875682;37875964;37876337;37876455;37881016;37885680;37886572;37888385;37890111;37891058;37891203;37891425;37896253;37897096;37899016;37899388;37899412;37899529;37899709;37900472;37902568;37906035;37906463;37910254;37913714;37914257;37914876;37915248;37915554;37916431;37917927;37922012;37922190;37923928;37924244;37924815;37925200;37926213;37927277?page=1&pagesize=100&order=desc&sort=creation&tagged=java&site=stackoverflow&filter=!-MObZ6A82KZGZ3WvblLvUKz1bWU5_K147&key=myApiKey
In the result I found this question in my JSON:
{"nr":7,"owner_id":3729911,"reputation":83,"creation_date":1466672851,"title":"Need a api or widget like Outlook calendar to create Appoitments","answer_count":0,"question_id":37987057,"is_roomba":true,"tags":["java","c#","quartz-scheduler"],"score":-2,"accepted_answer_id":0,"comments_count":0,"close_vote_count":4,"delete_vote_count":0,"view_count":10}
As you see, (if >10K) the question was deleted 8 hours before my API calls.
The problem can be fairly easy reproduced (1 out of 5 times) by calling API for last 1000 questions in different high traffic tags like python, java, PHP, ios