I'll bet you're using:
Code:
ErrorDocument 404
http://www.example.com/index.php?main_page=page_not_found
This MUST be changed to:
Code:
ErrorDocument 404 /index.php?main_page=page_not_found
Look in the .htaccess file for this code.

The ErrorDocument directive must NOT contain a domain name.