You can't change the image server if it isn't yours, but you can trivially write something on your own server to handle it for you.
First write something in your server-side language of choice (PHP, ASP.NET, whatever) that:
- Hits http://a.random-image.net/handler.aspx?username=chaosdragon&randomizername=goat&random=292.3402&fromrandomrandomizer=yes and downloads it. You generate a key in one of two way. Either get a hash of the whole thing (MD5 should be fine, it's not a security-related use so worries that it's too weak these days don't apply). Or get the size of the image - the latter could have a few duplicates, but is faster to produce.
- If the image isn't already stored, save it in a location using that key as part of its filename, and the content-type as another part (in case there's a mixture of JPEGs and PNGs)
- Respond with an XML or JSON response with the URI for the next stage.
In your client side-code, you hit that URI through XmlHttpRequest to obtain the URI to use with your images. If you want a new random one, hit that first URI again, if you want the same image for two or more places, use the same result.
That URI hits something like http://yourserver/storedRandImage?id=XXX
where XXX is the key (hash or size as decided above). The handler for that looks up the stored copies of the images, and sends the file down the response stream, with the correct content-type.
This is all really easy technically, but the possible issue is a legal one, since you're storing copies of the images on another server, you may no longer be within the terms of your agreement with the service sending the random images.