echo "<a href=mesaj_oku.php?sayfa=$onceki&cinsiyet=$cinsiye t&sehir=$sehir>Önceki</a> ";
Şeklinde yaparsan kod nereye gideceğini anlar ama bu tarz değişkenleri GET ile alabilirsin. Eğer ben POST ile bunları halledicem dersen, aramayı ilk yaptığı anda POST'tan gelen verileri cookie'ye yada session'a yazman gerekir. Yukarda verdiğim linkin benzerini FOR döngünde de kullanırsın. Sadece $onceki yerine $i yazarsın. Dediğim gibi yaparsan her hangi bir sorun çıkacağını düşünmüyorum.