Documentation around the
Database.emptyRecycleBin (which essentially is what happens when you click the button in the Recycle Bin too) says "After records are deleted from the recycle bin using this call, they can be queried using queryAll() for some time. Typically this time is 24 hours, but may be shorter or longer."
(added after the comment about REST API:) Visibility of stuff in the Recycle Bin doesn't look like something we have control over. If you can somehow expose this function to your REST app (by wrapping a piece of Apex like here) you could "hard delete" your records. But even then they'll stay visible, you'll just guarantee receiving DMLException if anybody tries to undelete them.
And yes, you can mix filtering by date fields,
SELECT Id, isDeleted, LastModifiedBy.Name, LastModifiedDate FROM Account WHERE CreatedDate = TODAY ALL ROWS and for deleted records LastModifiedBy will mean who & when has deleted them while for "normal" ones it will be last update.
I must say I'm a bit confused. Please write up more about your actual requirements? Essentially - do you want to show items in recycle bin or not :)
Edit again ;)
Sounds like most natural cut for your situation was done by smart guys at SF already.
1 normal query that gets all creates & updates
SELECT (all the fields you need) FROM Obj WHERE LastModifiedDate >= :lastUpsertSync
And another! query for deletes (you need only basic info that item was deleted after all, no need to retrieve details, right?)
SELECT Id FROM Obj WHERE isDeleted = true AND LastModifiedDate >= :lastDeleteSync ALL ROWS
If you're afraid you'll hit heap size limits or count of rows - simply add something like
ORDER BY LastModifiedDate ASC LIMIT 1000 clauses to both queries. Then whenever one of queries returns exactly 1000 you'll know there's risk you haven't retrieved full set. Then modify the variable that holds for example lastDeleteSync to value from last row and rerun the sync, ask user to hit the button again or whatever. Even better - use the queryLocator's id to retrieve next set of results (but before your session expires).