Quit thinking in terms of ints and pixels. Use meters as your units of measurement and floats to store them. It makes it much easier to reason about the dimensions of different objects, it's much more flexible and it avoids precision and overflow problems.
Let's suppose you want your map to take one hour to traverse on a fast jeep. How big should it be? If the jeep's speed is 100km\h, it's easy to tell that your map should be 100km wide. That's 100,000m. If your map is 100km by 100km, then the greatest possible distance between two objects would be sqrt(100000.0f * 100000.0f + 100000.0f * 100000.0f). You'll have no problems performing that calculation.
An important thing to note is that a proper engine will never check for collisions between objects so far apart. They obviously can't collide. You should at least divide your map into small rectangular regions (say, 20m by 20m) and only check for collisions between objects that are in the same region. Ideally, you'd implement quad trees for this kind of stuff.
For a complex game, you'll probably want to avoid having one giant map at all. There's no good reason to load it all into memory and process all of it when you can only see a small fraction of it at a time.