Why does WordPress Pagination Remove the Spaces from my GET Variable?

Not sure exactly how you’re adding “find” to the list of query variables, but this is the method you’re supposed to use:

function wpa_20565_query_vars( $public_vars ) {
    $public_vars[] = 'find';
    return $public_vars;
}
add_filter( 'query_vars', 'wpa_20565_query_vars' );

I use that to add custom pagination for my custom post types and custom filters for various other uses. It should make WP recognize and ignore the “find” query variable.

My next recommendation would be to enable the Debug Bar plugin and see what query it is WordPress is actually seeing. I’d also love to see the code you’re using to create the “next page” link that’s giving you a bad URL. It might also be partly responsible for the problems.