Oiço ambas as locuções, mas prefiro a segunda. Na primeira parece-me subentender-se nada ou outra coisa: antes de mais (nada / outra coisa).

Quando dizemos antes do mais, não se precisa de subentender seja o que for, porque o mais já significa só por si o resto, o restante, toda e qualquer outra coisa. A primeira, portanto, não é tão expressiva, na minha opinião.