Using fragments of online images in a paper I am preparing a paper and want to include some images from historical maps. There are several online examples and I want to snip a fragment (no more than 10% of the total image area), maybe clean it up a little, and use it in my paper. The fact that I'm only using a small part of the image and it's undergoing some transformative process seem like very reasonable grounds for claiming this is covered by 'fair use' but IANAL. However, suitable journals where I'd send my paper (of course) want all image rights/copyrights cleared in advance with my submission.

The online digital images almost invariably come from vendor sites who would like to sell me a print of the map for £££ and they are not going to give permission, even for non-commercial use. Although I could buy copies of the prints and scan them myself I'd prefer any more cost-effective suggestions.

This is different from How to use copyrighted images in an article? (they wanted to use the whole images) and Academic fair use and using publication images in your thesis (the images had already been published in books/papers and there was a publisher to approach)
As @jakebeal stated in his comment, the copyright for old maps from before 1900 should be expired. I can only comment on base of German Copyright Law:


70 years after the death of the creator, the copyright has expired.
A picture of a 2D object (for example a photograph of the Mona Lisa, a facsimile print of an original Luther's bible, a photocopy of an old map) is not protected by copyright since the threshold of originality is not reached. The aim is to reproduce the original as exactly as possible, hence there is no novelty and no input of ones own creativity. It seems, US law is similar here.


Conclusion: if your map is older than 100 years and copyright has expired, you would not have to ask the company for permission.
In case the map is not as old and copyright still applies, you would not be allowed to modify (also not to crop parts of it) the original without the consent of  the copyright owner.

Any way, you have to cite the source (the original creator of the map, not the company providing the copy).