Will the recovery messages also be sent in the order of the timestamp? What should our recovery mechanism be like?

You should process all the recovery messages and all the regular ones that come after them according to the timestamp, looking at the match ID. For example, in the case of the following Odds Change messages within the same match ID:

1. regular message
2. recovery message
3. regular message

You can discard 1., but you need to process 2. and 3.