Per-User caching does seem to be something that is going to be needed...
Depending on how many users are being tracked would storing the "reader_id" in an indexed array improve matters? " SELECT ... FROM message WHERE NOT (1 = ANY(reader_ids)) ; UPDATE message SET reader_ids = reader_ids || 1 WHERE messageid = ..." I'm not that familiar with how well indexes over arrays work or which kind is needed (i.e. gin/gist).
"is_read" is one of many properties being tracked for a message...
But you don't have to have all of them on the same table. Once you've identified the messages in question performing a standard join onto a supplemental detail table should be fairly straight-forward.
Do these other properties have values when "is_read" is false or only when "is_read" is true? Since you already allow for the possibility of a missing record (giving it the meaning of "not read") these other properties cannot currently exist in that situation.
