Had this problem myself a few months ago and I couldn't find a clean way round it. What I ended up doing was creating links to the next/previous on each display of the results. So if you are displaying page 3 the links would create a page variable with either a value of 2 or 4.
I then execute the whole query each time and use the mysql_data_seek function to seek to the relevant record by multiplying the page variable by, in your case, 25.
I then simply spool off the next 25 records in much the same way as you have. The thing I don't like is having to re-execute the full query every time, but I cannot at present see another easy way round it.
Regards,
chrber