Cuando restauras una copia de seguridad con esos mensajes en ella, la próxima sincronización de iCloud para Mensajes simplemente los borrará de nuevo, tal como viste con el dispositivo sin conexión. No conozco ninguna forma de deshacer/eliminar las operaciones de eliminación para esos mensajes en el historial de sincronización de iCloud para Mensajes.
Si quisieras experimentar, podríamos ver si hay alguna manera de ajustar los mensajes en (una copia de) la copia de seguridad para reintroducir esos mensajes como si fueran mensajes nuevos/diferentes y no los que iCloud para Mensajes ha registrado como eliminados. Eso si tienes paciencia, un dispositivo de repuesto para restaurar la copia de seguridad ajustada, y el número de teléfono y rango de fechas de los mensajes que deseas intentar recuperar ;)
También podrías optar por extraer los mensajes de las copias de seguridad de iOS que tengas con una aplicación de terceros (para la que soy desarrollador es Decipher TextMessage, también hay otras como iMazing y iExplorer). Eso no te ayudará a volver a fusionar el contenido en tu base de datos de iPhone/iCloud para Mensajes, pero te dará acceso a la información en ellos si eso es lo importante.