I've noticed that it that first 3 and last 3 never match. The malware or at least the one that I had focuses on matching the first 2 or 3 characters and that's it.
It's unable to match both first and last characters so it tries to math as many first characters as it can hoping the victim will not notice.
Matching the first and last 3 characters gives 38 billion combinations (58^6). Times 3 if you add all different address types (starting with 1.., 3.. and bc1q..). That means a 4 TB database is enough to accomplish this. And for 25% chance to find a match, just 1 TB is enough.
Existing malware may not do this yet, but I'm pretty sure it will happen eventually. So you can just as well get used to doing a much more thorough check before sending your coins.