Redfish, only an extra 10% of the map needs to be visible outside the range. That is enough to reach the horizon line, in which case there are images just like those of the sky which show distance.
Napalm, I don't have Rome on this computer, can you post an image of a Rome TW map when looking out towards the sea? I think that is the best example of faking a map going off into the distance. The actual terrain goes on for a very short distance beyond the actual playable bit, but a faked 2D panorama makes it seem far greater.
This is the best image I can find:

Note that the terrain in the foreground, just beyond the wall is real, and part of the map, but the mountains in the background are fake. They aren't 3D at all, but rather a 2D image made up to look 3D. You can sort of pick it in the change of lighting.
The game "Bontago" uses a similar idea of a 360 degree 2D panorama that encapsulates the screen, and gives the idea of infinite distance, despite the 3D camera, and limited space.
Here are some pics that explain it better than I can. Excuse the large sizes:
