Why don't you do the responsible thing and replace slow referrers with a randomly selected fast referrer from a predetermined pool of fast referrers?
@7of9: That's a good idea, I also planned to add it in the future. After I find the fastest, most stable and trustable referrer.
Until that time I advice you to use the RefControl Firefox add-on: https://addons.mozilla.org/en-US/firefox/addon/953 I also planned to mention this in the description. It's a useful add-on to hide the referrer even if you use "Unhide Referrer". This pair is useful if you want to keep hiding the referrer (for the original safety reasons, and with that add-on you can hide it absolutely everywhere), and at the same time will speed the process up.
I must add, RefControl may cause problems on some sites which are checking the the inner referrers. I found the "Forge" setting useful, that will show the root of every site as referrer, so won't leak unwanted information outside and works on most of the sites. Some are more strict and will drop an error if the referrer isn't exactly the same it gave, but you can control these with RefControl's black and white lists.