Using fragments of online images in a paper
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).