Théodore avait promis de verser une somme aux capitaines soit à Malaga, soit à Alicante. Dans aucun de ces deux ports, il ne put faire honneur à ses engagements. Les commandants ne voulurent pas aller plus loin, mais le baron qui, à défaut d'argent, n'était jamais à court d'arguments, déclara qu'aussitôt arrivé dans son royaume il fournirait, contre les munitions, des denrées de première qualité en grande abondance. Les officiers hollandais furent convaincus, et l'espérance au cœur, ils décidèrent de se rendre en Corse[ [462].
Pendant la traversée, Théodore causait volontiers avec Vastel. Il lui donna deux ducats et lui promit de le nommer colonel ou commandant d'un navire, s'il consentait à le suivre. Il apaisa une querelle que ce marin eut avec un officier pour une question religieuse: Vastel était catholique romain et il avait formellement refusé d'assister au prêche protestant. Neuhoff obtint que son protégé fût exempté de l'office luthérien[ [463].
Après avoir renouvelé leur provision d'eau en Espagne, les navires allèrent à Alger. Le Le Preterod entra seul dans le port, tandis que L'Agathe et le Jacob et Christine louvoyaient au large. Dès que le Preterod eut jeté l'ancre, le consul hollandais se rendit à bord dans une embarcation battant pavillon des États Généraux et conduite par vingt maures et un esclave français. Le capitaine reçut le consul à l'échelle du navire et l'introduisit immédiatement dans sa cabine où se trouvait le baron. Les trois personnages eurent une conférence qui dura trois heures. Le consul revint, y dîna quatre fois et resta deux jours entiers à causer avec Théodore[ [464].
Après un séjour de deux semaines, Le Preterod quitta Alger et rejoignit les deux navires restés en rade[ [465]. La flotille arriva le 14 août à Cagliari[ [466]. Deux jours plus tard, L'Africain, parti d'Amsterdam après les autres bâtiments, jeta l'ancre également dans le port sarde.
L'arrivée de ces vaisseaux éveilla les soupçons des consuls français et génois. Ce dernier, Mongiardino, écrivit à Mari le 17 août. Il envoya son rapport par un courrier spécial, qui partit un dimanche, à la pointe du jour. Il avait conservé un duplicata de sa lettre et se disposait, trois jours plus tard, à expédier cette copie lorsqu'il apprit bien des choses qui lui permirent de compléter ses renseignements. Il savait que le baron de Neuhoff se trouvait à bord d'un des bâtiments et l'opinion générale était que l'aventurier préparait une nouvelle descente en Corse. Mongiardino eut plusieurs conférences avec Paget, le consul de France. Celui-ci écrivit le 20 août à Boissieux, pour lui signaler la présence de Théodore dans les eaux sardes. Le vice-roi de Sardaigne, le marquis de Rivarola, envoya également le 21 août une relation à Boissieux sur l'arrivée de la flotille hollandaise[ [467].
Le 19 août, L'Agathe et Le Jacob et Christine appareillèrent. Le Preterod et L'Africain demeurèrent à Cagliari pour «ne pas faire semblant d'être du convoi»[ [468]. Les deux premiers bâtiments restèrent en vue pendant toute la journée du 20. Dans la nuit du 20 au 21, Le Preterod et L'Africain les rejoignirent[ [469].
Théodore et sa suite quittèrent le vaisseau de guerre et se rendirent à bord de L'Africain. Selon les uns, le capitaine Frentzel aurait déclaré que les ordres qu'il avait l'empêchaient d'aller plus loin. D'après Vastel, le baron changea de navire à cause d'une épidémie. Toujours est-il que Le Preterod se rendit à Port-Mahon. Arrivé là, François Vastel s'enfuit, pendant la nuit, à deux heures. Il gagna à la nage une tartane française des Martigues. Le Saint-Antoine, patron Alexandre Boyer, qui conduisit le déserteur à Alicante où, le 6 novembre 1738, il fit sa déclaration devant le consul de France[ [470].
Neuhoff ne désirait pas beaucoup revoir ses sujets. A peine fut-il sur L'Africain qu'il donna l'ordre au capitaine Keelmann de faire route directement sur Naples. Le commandant s'y refusa. Ses instructions l'obligeaient à se rendre en Corse. Bon gré, mal gré, on irait. Le roi dut se résigner à rentrer dans son royaume[ [471].
Les trois bâtiments, composant désormais la flotte du roi, parurent en vue de la Corse, le 14 septembre[ [472].
Comme L'Africain approchait des côtes, un oiseau se mit à voleter autour du mât. Soudain, il tomba inanimé aux pieds de Théodore. Au même moment, le navire donna contre un écueil. On crut qu'il allait sombrer, mais il reprit bientôt sa route. Le roi avait relevé la bête au plumage coloré; il la prit dans ses mains et la montra à ses officiers. L'oiseau revint à la vie et prit bientôt son vol vers l'île. Les compagnons du baron virent dans ce fait un signe de mauvais augure. Riesenberg, qui était un esprit fort, se moqua de ces gens superstitieux[ [473].