I lost my highwayman by getting into a random encounter, going from New Reno to Vault 15, and then not getting back in it. Will it return someplace?
The highwayman is incredibly bugged. You SHOULD have had a little event placed on your map that says something like 'Highwayman' or 'Refuel car' or something along those lines. If I remember rightly it's a tiny green circle - like a special encounter. If you haven't got that marked on your map then reload a save game before hand because you're not likely to get it back (although I have heard that on spectacularly rare occaisions it can turn up outside Vault City but I've never had this happen).
The boot also turns up in San Francisco on occasion. All you really need is the boot, and seeing as you probably haven't patched the game, chances are it'll pop up eventually.