Po pierwsze to zdecyduj się czy pierwsza strona jest numerowana od 0 czy 1

Bo jeśli od 0 to Ci się rypnie skrypt przy sprawdzaniu empty, który stronę 0 wychwyci jako pustą i wpisze tam 1, czyli de facto drugą.
Jeśli zaczynać chcesz od strony pierwszej to musisz od wyników odejmować 1 bo pierwszą partią jaką poślesz do bazy będzie LIMIT 5, 5 czyli pobierz 5 rekordów począwszy od 5, a nie o to Ci chyba chodzi, tylko LIMIT 0, 5

Stąd konieczność zmiany
if (empty($_GET['page']) || !is_numeric($_GET['page']) || $_GET['page'] < 1
) { $page = 1;
} else {
$page = $_GET['page']-1;
}
lub jak radzi Szeszek dopiero przy zmiennej $od odejmować 1.
No i wspomnianej strony Następna na o DWA większą (o jeden jeśli posłużysz się sposobem Szeszka), bo w końcu wcześniej zmniejszyłeś ją już o jeden

echo '<a href="search.php?page='.($page+2).'">następna</a>';
Inna sprawa, że głupotą jest tak robić bo nie masz ogranicznika i możesz nawet sobie od 3 strony mieć wyniki puste, ale możesz przechodzić sobie na kolejne do usranej śmierci bo link Następna nadal będzie się zwiększał. Musisz zrobić ograniczenie, które wyeliminuje dodawanie tego linku gdy osiągniesz ostatnie rekordy tabeli.