This will sort before doing the LIMIT:
ORDER BY lastname LIMIT 0, 300
What is the actual query?
How do you do page 2? Were there any INSERTs or DELETEs between showing page 1 and page 2?
Pagination via LIMIT has two problems:
* Performance
* INSERT/DELETE can cause symptoms like you mention.
Here are some references:
http://forums.mysql.com/read.php?10,360578 (join in union)
http://forums.mysql.com/read.php?115,355941 (Query that returns indexed fields involves FILESORT, why?)
http://forums.mysql.com/read.php?24,291646 (Very Slow Simple Query)
http://forums.mysql.com/read.php?10,292296 (break mysql query? Is this possible in my sql)
http://forums.mysql.com/read.php?125,246731 (Alternative to FOUND_ROWS())
http://forums.mysql.com/read.php?10,243777 (Query performance question (using index slows down?))
http://forums.mysql.com/read.php?24,240838 (Slow search query)
http://forums.mysql.com/read.php?10,239876 (Query performance on database with joins)
http://forums.mysql.com/read.php?24,234339 (MySQL Performance Tuning on my server)