Initial conditions for systems described in state space - LTI or not?
If you look at Chapter 5 of:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-011-introduction-to-communication-control-and-signal-processing-spring-2010/readings/MIT6_011S10_notes.pdf

which is entitled "Properties of LTI State Space Models" , equation 5.33 doesn't seem to have a problem with initial conditions, or any other book (I stand corrected, there is one book) that I'm aware of.  Unless Oppenheim was touched with insanity, I'm inclined to accept his characterization that initial conditions don't disqualify a LTI system as "not linear" by his use of the term "zero input linear".

At the beginning of the notes, (and in Oppenheim and Shaefer 3rd edition) a LTI system is given as:

$$
y[n]=\sum_{k=-\infty}^{\infty} x[k] h[ n -k]  
$$
 which doesn't require $h[n]$ to be causal or stable.  $x[n]$ doesn't have to satisfy $x[n]=0 \;\text{for} \; n &lt;0$ .

There is emphasis  in the text that one needs to consider the entire history of $x[n]$, not just for $n \ge 0$.

let $$x[n] = \hat{x}[n]+\tilde{x}[n] $$
  where 
$$ \hat{x}[n] = \begin{cases} x[n]\; \text{for}\; n&lt;0 \; \text{and}\\
0 \; \text{for}\; n\ge 0 \end{cases}$$ 

and 
$$ \tilde{x}[n] = \begin{cases}0\; \text{for} \; n&lt;0 \; \text{and}\; \\ x[n] \; \text{for}\; n\ge 0 \end{cases}$$
 by linearity.

$$
y[n]=\sum_{k=-\infty}^{-1} \hat{x}[k] h[ n -k]  + \sum_{k=0}^{\infty} \tilde{x}[k] h[ n -k] 
$$
if $y[n]$ is causal,
$$
y[n]=\underbrace{\sum_{k=-\infty}^{-1} \hat{x}[k] h[ n -k]}_{\text{zero input linear}}  + \underbrace{\sum_{k=0}^{n} \tilde{x}[k] h[ n -k]}_{\text{zero state linear}}, \quad n \ge 0
$$

The essential point is that initial conditions account for prior input.  Where $n=0$ is referenced for $x[n]$ is arbitrary, which is another manifestation of time invariance.  Initial conditions are not some arbitrary value vexing the system.  if $x[n] = 0 $ for $n &lt;0 $ the initial conditions are zero.  

Let's try something else. Let $z[n]=\tilde{x}[n+1]$ (advance by one sample) and with $\tilde{x}[n]$, the system was LTI without controversy.
But now, 
$$
y[n]=\underbrace{ z[-1] h[n]}_{\text{zero input linear}}  + \underbrace{\sum_{k=0}^{n} z[k] h[ n -k]}_{\text{zero state linear}}, \quad n \ge 0
$$
and now we have an initial condition. A forward shift of 1 sample would make an LTI system nonlinear? 

The logical fallacy at the root of question is to use the definition of zero state linearity and applying it to the zero input case.