Like lots of other things in the world of Fallout, the term "between" is used loosely. The location you are looking for is called the Nipton Road Rest Stop, located a little bit north of the Mojave Outpost. When you take the road from Nipton to Mojave Outpost, instead of heading up the hill past all the wrecked cars and trucks, continue north on the flat road. You should be able to see it from the spot where you come across all those destroyed vehicles that I mentioned. Anyway, the gas station there is his safe house. It has a handful of items, including a note from the mayor. I honestly can't remember everything I found in there, because I ended up at that location before I ever made it to Nipton. Don't miss the star bottle cap on the counter near the cash register.