Я думаю, что проще всего было бы сохранять токен в БД при каждом сохранении чего-либо в БД и связывать с ним все измененные объекты. Когда клиент запрашивает новые данные, он передает последний полученный токен серверу и ответ сервера с объектами, связанными с токенами, сгенерированными с момента получения токена клиентом.
Как вы храните данные на стороне клиента - это решение, которое вы должны принять. Но речь идет не об использовании NSMutableArray или NSMutableDictionary, а о том, как сохранить его на устройстве. Я бы посоветовал вам взглянуть на CoreData, но возможен также прямой SQLite или plist.
И, конечно, вы можете использовать словарь и массивы одновременно. то есть вы можете иметь большой массив со всеми записями, упорядоченными по дате, и помещать одни и те же объекты записей в словарь с ключами для даты.