Wo deine Aussreisser herkommen kann ich jetzt genau auch nicht sagen.
Ich vermute das es sich dabei um einen Überholeffekt handelt.
Der Timer0 Overflow Interrupt wurde ausgelöst kann aber den Überlaufzähler nicht inkrementieren, weil ein anderer Interrupt gerade läuft und das SEI Flag somit gelöscht ist.
Der TCNT0 ist dann auf 0 ohne den Überlaufzähler NumberOverflow0 zu inkrementieren.
Das Problem würde sich verbessern, wenn du für beide Routinen den Timer 1 verwenden würdest, da dieser 16 Bits hat und der Fehler dadurch wesentlich seltener auftritt.
Ausserdem brauchst Du bei deiner Methode immer 2 interrupt Zyklen um die Drehzahl zu bestimmen.
Wenn du, während der INT0 / ICP Interruptroutine, den Zählerstand der vorherigen Messung in den OLD Vektor schiebst und den neuen Zählerstand in den NEW Vektor einließt kannst Du bei jeder Flanke eine Drehzahlmessung vornehmen.
Das heisst es geht doppelt so schnell.

Ausserdem würde ich noch ein Timeout einbauen um den Leerlauf, sowie einen stehenden Motor zu detektieren.

z.B. 2 sek kein Geschwindigkeitssignal aber Drehzahlsignal vorhanden = Leerlauf.
2 sek gar kein Signal = Motor aus.

Ausserdem würd ich das Programm mal mit dem Simulator vom AVR Studio austesten - sollte mit AVR GCC gehen.

Ich benutz leider Codevision AVR und kann deshalb dein Prog nicht austesten.