Usando una variable 'Extra long' (cuya existencia desconocia. Muchas gracias bokeaus), no obviarás el problema de millis(), ya que es la propia función milis() la que se resetea a los 50 dias. Por tanto, no cambia nada entre usar una variable long y una long long.
Con respecto a lo que comenta el compañero Chiva, apuntarte que podrias tener problema si el overflow se produce entre la asignacion de milis() a la variable y su evaluacion:
cuando asignas, imaginate que millis() esta a punto de desbordarse, y vale una barbaridad. Antes de evaluarla, se desborda, y cuando haces la comparación, pasa a valer 3 (por decir algo) entonces, y durante los proximos 50 dias, millis()-tiempo sera menor que cero, y el while se estara ejecutando permanentemente.
Supongo que bastará con hacer un if millis-tiempo<0 dentro del while para eliminar del todo el problema.