Мое мнение, что хранить в зависимости от логики приложения. если повторно отправка пуша допустима, то храните на телефоне, если нет, то на сервере.
Учтите, что пользователь может удалить приложение, обновить прошивку, или просто поменять аппарат, что приведет к потере информации о пуше.