Единственное решение, о котором я могу подумать, - это создать уведомление в Сервисе, которое запускается в ответ на намерение BOOT_COMPLETED_ACTION.
Для получения Notification вы, вероятно, можете обойтись, просто сделав это в BOOT_COMPLETED_ACTION BroadcastReceiver, а не делегировав его службе. Тем не менее, я согласен, это единственный способ сделать это AFAIK.
Только убедитесь, что вы не раздражаете своих пользователей этим. Большинство людей ожидают относительно чистого листа при перезагрузке телефона. Android предполагает, что уведомления больше не актуальны при перезагрузке, поэтому они не сохраняются.
Так, например, предположим, что вы писали почтовый клиент и используете уведомления, чтобы сообщить пользователю о непрочитанных сообщениях. Ответ не должен быть «заново отображать уведомление о непрочитанном сообщении после перезагрузки». Ответ должен быть «проверить непрочитанные сообщения после перезагрузки и поднять уведомление, если есть непрочитанные сообщения». Таким образом, если нет непрочитанных сообщений (например, пользователь какое-то время выключил телефон и позаботился о своей электронной почте на ПК или планшете), он не получит ложное уведомление.