I think that those messages are executed again. When a view-change happens, all the nodes would be in the same checkpoint. When the "new" primary for the view v + 1 receives 2⨍ valid view-change messages, multicasts a new-view message.
In the message that is sent, it indicates: V: set of received and valid view-change messages. P: set of pre-prepared unprocessed messages. These messages are calculate as follows: From the last stable checkpoint, you get the sequence number of the last executed request. This value will correspond to the min-s. Take the largest sequence number of all prepared messages you have received.
This value will correspond to the max-s. As a result, it generates as many pre-prepared messages as needed. Each node saves the log of the messages that are not inside a chekcpoint, so they don't need to be procesed again.