FuzzyRowFilter skips valid rows

The issue may affect not only master branch, but previous releases as well.
This is from one of our customers:

We are experiencing a problem with the FuzzyRowFilter for HBase scan. We think that it is a bug.
Fuzzy filter should pick a row if it matches filter criteria irrespective of other rows present in table but filter is dropping a row depending on some other row present in table.

Details/Step to reproduce/Sample outputs below:

Missing row key: \x9C\x00\x044\x00\x00\x00\x00
Causing row key: \x9C\x00\x03\xE9e\xBB{X\x1Fwts\x1F\x15vRX

Prerequisites
1. Create a test table. HBase shell command – create 'fuzzytest','d'
2. Insert some test data. HBase shell commands:
• put 'fuzzytest',"\x9C\x00\x044\x00\x00\x00\x00",'d:a','junk'
• put 'fuzzytest',"\x9C\x00\x044\x01\x00\x00\x00",'d:a','junk'
• put 'fuzzytest',"\x9C\x00\x044\x00\x01\x00\x00",'d:a','junk'
• put 'fuzzytest',"\x9C\x00\x044\x00\x00\x01\x00",'d:a','junk'
• put 'fuzzytest',"\x9C\x00\x044\x00\x01\x00\x01",'d:a','junk'
• put 'fuzzytest',"\x9B\x00\x044e\xBB\xB2\xBB",'d:a','junk'
• put 'fuzzytest',"\x9D\x00\x044e\xBB\xB2\xBB",'d:a','junk'
Now when you run the code, you will find \x9C\x00\x044\x00\x00\x00\x00 in output because it matches filter criteria. (Refer how to run code below)
Insert the row key causing bug:
HBase shell command: put 'fuzzytest',"\x9C\x00\x03\xE9e\xBB{X\x1Fwts\x1F\x15vRX",'d:a','junk'
Now when you run the code, you will not find \x9C\x00\x044\x00\x00\x00\x00 in output even though it still matches filter criteria.

Verified the issue on master.