This seems like a bug. I encountered it on Joomla with 4.6.8 and reproduced on the demo server.
If I create a case and change the status to "Urgent", then use the API (including API explorer), it seems to filter properly on status_id and is_deleted UNTIL I also add contact_id (Case Client). Then it returns the case regardless of its status. (I didn't test whether it works correctly with is_deleted).