in your .htaccess to overwrite your servers configuration and trigger Joomla's built in handler. Also ensure that your server is configured to allow rewriting of urls. You should use the default Joomla htaccess.txt as a base for your own .htaccess file, with the inclusion of the above two lines.
This probably is because you don't use the .htaccess file (or it hasn't been correctly configured).
When typing your URL withoutindex.php, it gives the standard 404 error page because Joomla is not even loaded, and can't present the custom 404 error page (I'm assuming this - not sure about the technical details).
Try renaming htaccess.txt to .htaccess in your Joomla root folder. You might have to uncomment the following line, but this depends on your server settings:
You should now get your custom error page for all your examples above.
error.phpfile to pastebin.com so we can take a look?