Page not found using paginate_links() with a no logged user

I get a very very strange problem.
I have a page with a custom search:

    global $query_string; 

    $paged = (get_query_var('paged')) ? get_query_var('paged') : 1;

    $the_query = new WP_Query();
    $the_query->query($query_string.'&paged='.$paged.'&posts_per_page=50&post_status=any');

    while ( $the_query->have_posts() ) : $the_query->the_post(); 

it works correctly I see 50 posts per page.
The problem is that for the pagination i need to show something like:

1 2 3 4 last >>

I found this useful wordpress function paginate_links()

But there is a very strange error…. If I’m logged I CAN see the secord, third … pages, if I’m NOT logged I get 404 not found!

How is this possible?
The urls are:

http://www.example.com/date/2012?cat=8

http://www.example.com/date/2012/page/2?cat=8

(archive.php)

So, I must to be logged to see second, third etc etc pages, otherwise I only cann see the first!

How can I solve it?
Thanks