Fallout Wikia has some tips on recovering lost companions who do not appear in either their original location or the Lucky 38. I have not had this problem myself so cannot test.
Update: I can confirm the Vault 22 method worked for me; successfully recovered Rex (on PC).
For Consoles and PC
Here the given trick is to go to Vault 22 and use the central elevator (requires repair skill level 50).
Choose to go to Level 5 - Pest Control.
The missing Companion(s) may be waiting there at the exit of the elevator, you may need to talk to them and ask them to follow you (ie, they may be stuck in wait mode).
For PC
This involves using the console commands, I highly recommend saving before messing with the console, and as per Xantec's comment you should be aware this will disable Steam achievements for that play session (ie, you need to fix the game then save and restart).
Here <red_id>
is an internal number for the companion - for Veronica this seems to be 000e32a9
- you can get the ID's of others from the Wikia site as well.
This will move the companion to your location:
prid <ref_id>
moveto player
This will move you to the companions current location:
player.moveto <ref_id>
If these don't work the recommendation is to kill and resurrent the companion. First use these two:
prid <ref_id>
OpenTeammateContainer 1
This should give you their inventory windows - empty it into your own.
Then do the following, and hopefully the companion should be back:
moveto player
resurrect 1
disable
enable