What statistics do you have on the data? I suppose most messages are read by low number of users, mostly 0 or one.
I can see two options to consider:
1) Use arrays to store information on which users have already read the message. You may need GIN/GIST index to search fast.
2) Introduce some kind of special column(s) for the cases when the message is unread by everybody or was read by at most one user. E.g. read_by columns with null value for unread, special value for read by many and real user if read by only one.
in this case your condition would be (read_by is null or read_by not in (current_user or special_value) or (read_by = special_value and not exists()). Note that optimizer may have problems with such a complex expression nd you may need to use "union all" instead on "or". Partial index(es) for null/special value may help.
Best regards, Vitalii Tymchyshyn