Hm... It turned out that
[SELECT Id FROM Account ALL ROWS]
works just fine even if you Empty Recycle Bin. There might be a gap of 14 days, when this SOQL become ineffective. I have deleted records only for last 14 days. Maybe coincidence.
However, it is strange, because Querying All Records with a SOQL Statement says that you can query from Recycle Bin. Interesting... Maybe a bug.