You’ll need to open the xml file and manuall do a search and replace for the old URL and replace it with the new URL (It sounds like you’re using the import plug-in, if not you’d open the SQL DB File to make the changes).
You can use NotePad++ for a simple search and replace. Since the images aren’t on your older server, you’ll need to place then on the new server and amend the search and replace “replace” value with the new URL. You’ll need to be sure to catch all “Hard Coded” URL’s EXAMPLE:
Search:
http://youroldwebsite.com/wp-content/uploads/2011/09/
Replace:
http://yournewsite.com/wp-content/uploads/2011/09/
You would just need to be sure that you replace all image dates (Month/Year) to reflect the actual folder you put them in. In my example every image that was hard coded would need to be replaced to trick WP into thinking they were all uploaded on 2011/09, which is what you’d have to name the folders for it to work. The search should also catch the post meta since you won’t be uploading the DB or will you? If so, you’ll need to update that as well.
Not completely effortless, but it might be better than manually replacing them depending on the amount of images you have.