Si tes messages datent de moins de 30 jours, il sont encore sur la messagerie de SFR si tu l'interroges directent (au 123, je crois). Après pour les re-récupérer sur l'iPhone, je ne sais pas.
Sinon, c'est effectivement très bizarre ces messages qui disparaissent après changement de carte SIM, et en plus, qui ne sont pas récupérés par la restauration d'une sauvegarde. Si tu as sauvegardé ton iPhone avec tes messages vocaux, il me semble qu'ils sont forcément dans le dossier de ton ordinateur, mais quelque chose fait qu'ils ne sont pas restaurés (une date limite, où je ne sais quoi, mais là c'est trop technique pour moi).
Reste l'option d'extraire directement tes messages perdus dans le dossier de sauvegarde de l'iPhone qui est sur ton mac. Hélas, c'est impossible à faire directement, mais il me semble avoir utilisé un logiciel ad-hoc pour récupérer des trucs, il y an un an ou deux. Désolé si tout ça est très vague et ne t'aidera probablement pas beaucoup
Edit : voilà, j'avais utilisé ça :
http://www.iphonebackupextractor.com/