Q:

How do you prepare for out of memory conditions? 

This can be easy for games with well defined scope, but the question is about sandbox games, where the player is allowed to create and build anything. 
Possible techniques:

Use memory pools with upper limit. 
Delete objects that are no longer needed periodically. 
Allocate extra amount of memory at the beginning so it can be freed
later as a recovery mechanism.  I would say around 2-4 MBs. 

This is more likely to happen in mobile/console platforms where memory is usually limited unlike your 16 GB PC.  I am assuming you have full control over memory allocation/deallocation and no garbage collection involved.  That's why am tagging this as C++. 
Please note that I am not talking about Effective C++ Item 7 "Be prepared for out-of-memory conditions", even though it's relevant, I would like to see an answer more related to game development, where you usually have more control over what's happening. 
To summarize the question , how do you prepare for out of memory conditions for sandbox games, when you are targeting a platform with limited memory console/mobile ? 

A:

Generally, you don't handle out-of-memory.   The only sane option in software as large and complex as a game is to just crash/assert/terminate in your memory allocator as soon as possible (especially in debug builds).   Out-of-memory conditions are tested for and handled in some core system software or server software in some cases but not usually elsewhere. 
When you have an upper memory cap you instead just ensure that you never need more than that amount of memory.   You can keep a maximum number of allowed NPCs at a time, for instance, and simply stop spawning new non-essential NPCs once that cap is hit.   For essential NPCs you can either have them replace non-essential ones or have a separate pool/cap for essential NPCs that your designers know to design around (e.g. if you can only have 3 essential NPCsa, the designers will not put more than 3 in an area/chunk - good tools will help designers do this properly and testing is essential of course). 
A really good streaming system is also important especially for sandbox games.   You don't need to keep all NPCs and items in memory.   As you move through chunks of the world new chunks will be streamed in and old chunks streamed out.   These will generally include NPCs and items as well as terrain.   Design and engineering caps on item limits need to be set with this system in mind, knowing that at most X old chunks will be kept around and pro-actively loaded Y new chunks will be loaded, so the game needs to have space to keep all the data of X+Y+1 chunks in memory. 
Some games do attempt to handle out-of-memory situations with a two-pass approach.   Keeping in mind that most games have a lot of technically unnecessary cached data (say, the old chunks mentioned above) and a memory allocation might do something like:
allocate(bytes):
  if can_allocate(bytes):
    return internal_allocate(bytes)
  else:
    warning(LOW_MEMORY)
    tell_systems_to_dump_caches()

    if can_allocate(bytes):
      return internal_allocate(bytes)
    else:
      fatal_error(OUT_OF_MEMORY)

This is a last-stop measure to deal with unexpected situations in release but during debugging and testing you should probably just immediately crash.   You don't want to have to rely on this kind of stuff (especially because dumping the caches may have some serious performance consequences). 
You might also consider dumping high-res copies of some data, for instance you might dump the higher-resolution mipmap levels of textures if you are running low on GPU memory (or any memory in a shared-memory architecture).   This usually requires a lot of architectural work to make worth it, though. 
Note that some very unlimited sandbox games can be rather easily just crashed, even on PC (remember that the common 32-bit apps have a limit of 2-3GB of address space even if you have a PC with 128GB of RAM; a 64-bit OS and hardware allows more 32-bit apps to run simultaneously but can't do anything to make a 32-bit binary have a larger address space).   In the end, you either have a very flexible game world that will need unbounded memory space to run in every case or you have a very limited and controlled world that always works perfectly in bounded memory (or something somewhere in between). 

A:

The application is usually tested on the targeted platform with the worst case scenarios and you will always be prepared for the platform you are targeted.  Ideally the application should never crash, but other than optimization for specific devices, there are little choices when you face low memory warning. 
The best practice is to have preallocated pools and the game uses from the very beginning all the needed memory.  If your game has a maximum of 100 units than have a pool for 100 units and that's it.  If 100 units exceeds the mem requirements for one targeted device then you can optimize the unit to use less memory or change the design to a maximum of 90 unit.  There should be no case where you can build unlimited things , there should always be a limit.  It would be very bad for a sandbox game to use new for each instance because you can never predict the mem usage and a crash is a lot worst than a limitation. 
Also the the game design should always have in mind the lowest targeted devices because if you base your design with "unlimited" things in it then it will be a lot harder to solve the memory problems or change the design later on.