Simple yet problematic update query
While I'm not convinced this is a problem with the query itself (did you check for blocking when it runs slow? did you check the wait type(s) occurring while it was running), IN and OR can be a problematic pattern to optimize for. Have you considered breaking this into multiple statements?

UPDATE dbo.VillageSemaphoreset 
  SET [TimeStamp] = GETDATE() -- TimeStamp is a terrible column name btw 
  WHERE VillageID = @X;

UPDATE dbo.VillageSemaphoreset 
  SET [TimeStamp] = GETDATE()
  WHERE VillageID = @Y;

IF (whatever condition leads you to "sometimes add this OR")
BEGIN
  UPDATE v 
    SET [TimeStamp] = GETDATE()
    FROM dbo.VillageSemaphoreset AS v
    WHERE VillageID = @Z
    AND EXISTS 
    (
      SELECT 1 FROM dbo.VillageSU AS vs
      WHERE vs.VillageID = v.VillageID
    );
END


This may solve the estimation problem, but I agree with Max, a statistic with a leading column of UnitCount won't help the estimates for these queries anyway.