Pagination in a POST search form/results

[eluser]gh0st[/eluser]
Here's my situation.

1. A form where a user selects data to search upon.
2. A user presses 'go' and a MySQL search is performed.
3. The results are displayed, paginated, starting at page 1.

However, whenever I press on page 2 - the data is lost.

This is because the data is being sent in a POST format.

In addition, if a user presses F5, or wants to go back then a message comes up -- which means a POST processing file has to be in place to prevent issues.

I've looked around the forum, and there are several threads on the same subject, such as:
http://ellislab.com/forums/viewthread/71061/

There appears to be several ways around this -- but which one is the right one?

1) enable_query_strings = TRUE
outputs: (example.com/index.php?c=controller&m=function)

2) use sessions.
Problem: I'm coding it for a very big site and I don't like the idea of storing things in sessions or cookies for security and memory issues.

3) store all searches in a table, use a session to reference it.
Problem: If there's loads of searches performed by lots of people on a traffic heavy website.

4) Use URI base64 encoding/decoding.

5) Use URI segments which tell CI what to do with it.

I'm leaning towards 1, but this will sacrifice clean FURLS -- I'm wondering:

>> What's the right way to do it (assuming someone's already cracked it)?

Thanks.