Desembarazado de este incidente, se apresuró a ir en persecución del Mismo Mitridates, porque esperaba encontrarlo en la Bitinia, detenido por Voconio, a quien él había enviado hacia Nicomedia con algunas naves para molestarle en su fuga; pero Voconio se había retrasado en Samotracia, con motivo de iniciarse y celebrar los misterios, y a Mitridates, que navegaba con su armada y se daba priesa por llegar al Ponto antes que volviese Luculo, le sobrecogió una terrible tormenta, con la que unas naves se le desaparecieron y otras se le fueron a pique. Toda la costa se vio por muchos días cubierta de despojos navales, arrojados a la orilla por las olas; y como el transporte en que él mismo navegaba no pudiese ser traído a tierra por los pilotos, a causa de la gran borrasca y de estar las olas tan enfurecidas, ni tampoco aguantar en el mar, por ser muy pesado y hacer agua, trasladóse a un buque de los de corso, y poniendo su persona a merced de los piratas, por un modo increíble y extraño llegó salvo a Heraclea de Ponto. No le salió, pues, mal a Luculo la jactancia de que usó ante el Senado, porque habiendo decretado éste que con tres mil talentos se dispusiese la armada para aquella guerra, se opuso a ello, mandando cartas en que se gloriaba de que sin tantos gastos y preparativos arrojaría del mar a Mitridates con solas las naves de los aliados; lo que así cumplió con el auxilio de los Dioses, porque se dice haber sido para los del Ponto aquella tormenta castigo de Ártemis Priapina, por haber saqueado su templo y robado su imagen.