IRO>сначало подумал ввести счетчик для писем и ревизию для людей, но получилось так что в каждой ячейке должна быть своя, и опять вернулся к N*M

Можно сделать общий генератор id для всех ячеек, если такой можно сделать. Ну или хранить, скажем, время прихода письма.
Тогда каждый человек помнит наибольший id пиьсма, который он читал или время прихода такого письма. Человек подходит к ячейке, смотрит есть ли там письма с большим id или большим временем и читает их, а потом увеличивает запоминает id или время.