Trying to find a better way to do this

Users.cs

/*
  I am using the cache here as a persistence layer, so I need to have a deterministic way at minimum
  of knowing where to look for an object.

  Problems that I already know exist: Currently I risk overwriting a list that has different items, perhaps I should only add and remove from teh Update section?

  Thoughts better ways of handling the item changes from the time I fetch them from the cache until I read it from the cache.

  Maybe instead of modifying the list I read out of the cache I should just send the update directly to the cache?

*/


public static List<string> GetUsers()
{
    //This is the ServiceStack ICacheClient
    ICacheClient cache = //Resolve Cache From IoC Container
    return cache.Get<List<string>>(UserKey);
}

public static void UpdateUsers(List<string> NewUsers)
{
   //This is the ServiceStack ICacheClient
    ICacheClient cache = //Resolve Cache From IoC Container
    cache.Set<List<string>>(UserKey, NewUsers);
}

//This is just a sample method
public static void ModifyUsers()
{
   var Users = GetUsers() ?? new List<string>();
   Users.Add("New User");
   UpdateUsers(Users);
}

What reason are you updating the cached list? If from your datastore I would suggest your last thought. Just send the fresh result from the datastore to the cache. I can see a potential problem with multiple threads hitting the ModifyUsers at once. If the update to the cache is coming from the UI (not sure why) then I'd be curious why that is the case.

Also may I suggest putting the coalesce operation in the GetuUsers method so you can be sure that whenever you call it you will get something. Don't make the caller deal with null if an empty list is okay for them to work with.