I had this exact same problem too.
Using an absolute URL for the location of the 404 error page made all links on the 404 page work but didn't pass the (not found) URL of the original request to the 404 page.
Using a relative URL for the 404 page location meant the URL of the requested but not found page was passed to the 404 page so i could display it in the 404 page but then links on the 404 page failed as described by Busman.
My solution was to use a relative URL for the 404 error page, the 404 error page was passed the URL that was not found and then the 404 page redirected to itself with an absolute URL passing the URL of the original not found page to itself.
It works but is a bit clumsy and probably a waste of server resources - so i'll be rewriting my 404 page later today and trying the html BASE tag trick to see if it works better than my existing technique.
Thanks for the tip

warwound