Você deve usar o comando HSCAN.
Por exemplo:
redis> HMSET address_book bob_123456 Address1 mary_567894 Address2 john_123456 Address3
OK
redis> HSCAN address_book 0 match *_123456
1) "0"
2) 1) "bob_123456"
2) "Address1"
3) "john_123456"
4) "Address3"
Atualizar
Implementação do Python:
r = Redis(....) #redis url
for address in r.hscan_iter('address_book', match='*_123456'):
print(address)