Are you deleting messages after you receive them? I haven't run into any race conditions but I suppose if I did, I'd use redis's HyperLogLog or something similar to see if I've already processed the message.
HyperLogLog is for cardinality estimation, not set membership. A bloom filter would be more appropriate I believe.