Is entanglement *not* intrinsic to state, but dependent on division into subsystems? (Susskind QM) I'm working through Susskind's "Quantum Mechanics" book (TTM series), which I quite like.
Background
In Lecture 7 (Chapter 7), he studies a 2-spin system. A single spin has eigenvectors: 
$$|u\rangle=\begin{pmatrix}1\\0\end{pmatrix},~~
|d\rangle=\begin{pmatrix}0\\1\end{pmatrix}$$
and then a 2-spin state has eigenvectors:
$$|uu\rangle=\begin{pmatrix}1\\0\\0\\0\end{pmatrix},~~
|ud\rangle=\begin{pmatrix}0\\1\\0\\0\end{pmatrix},~~
|du\rangle=\begin{pmatrix}0\\0\\1\\0\end{pmatrix},~~
|dd\rangle=\begin{pmatrix}0\\0\\0\\1\end{pmatrix}$$
Alice studies the first with an operator $\sigma$ and Bob the second with an operator $\tau$ (these are really product operators of single-spin $\sigma_z$ with the identity $I$: $\sigma_z\bigotimes I$ and $I\bigotimes\sigma_z)$:
$$\sigma =
\begin{pmatrix}
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 \\ 
0 & 0 & -1 & 0 \\ 
0 & 0 & 0 & -1
\end{pmatrix}
~~~
\tau =
\begin{pmatrix}
1 & 0 & 0 & 0 \\ 
0 & -1 & 0 & 0 \\ 
0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & -1
\end{pmatrix}$$
Now for the interesting stuff.
We can have a product state where the two spins ("subsystems") are independent (no entanglement):
$$\psi ~=~ (a_1|u\rangle+a_2|d\rangle)\bigotimes(b_1|u\rangle+b_2|d\rangle)$$
$$~~~=~a_1b_1|uu\rangle+a_1b_2|ud\rangle+a_2b_1|du\rangle+a_2b_2|dd\rangle~~~(1)$$
where the $a_i$ and $b_i$ are separately normalized to $1$ so that if we calculate the expectation for either spin the other does not factor in at all. For example $\langle\psi|\sigma|\psi\rangle=a_1^2-a_2^2$ with no appearance of the $b_i$.
Then Susskind says that most randomly chosen coefficients of the $|uu\rangle...$ (normalized) will not factorize as in $(1)$. Then they are entangled. And an example of a maximally entangled state is the singlet state:
$$|S\rangle=\frac{1}{\sqrt 2}(|ud\rangle-|du\rangle)$$
Now $\langle S|\sigma|S\rangle=0$ so you have zero information about the individual spins. However, you have information about correlated measurements, because $\langle S|\tau\sigma|S\rangle=-1$ where by matrix multiplication
$$
\tau_z\sigma_z = 
\begin{pmatrix}
1 & 0 & 0 & 0 \\ 
0 & -1 & 0 & 0 \\ 
0 & 0 & -1 & 0 \\ 
0 & 0 & 0 & 1
\end{pmatrix}
$$
Susskind then discusses how you can test whether a state is entangled or not (and how much entangled) by computing the correlation of operators $A$ and $B$, or checking the eigenvalues of single-state density matricies ($\rho_{2x2})$, which should be $\{1,0,0,0...\}$, or checking if the state coefficients $\{0,\frac{1}{\sqrt 2},-\frac{1}{\sqrt 2},0\}$ can factorize as in $(1)$ (they can't).
Question (rewritten after helpful answers by tparker and Emilio Pisanty)
Aren't these entanglement tests all relative to the chosen 4x4 operators, $\sigma_z$ and $\tau_z$, which reflect a particular choice of dividing the state into subsystems?
Instead of a subdivision based on the two spins, we can subdivide based on $|S\rangle$ and the triplet states $|T_1\rangle=\frac{1}{\sqrt 2}(|ud\rangle+|du\rangle),~~|T_2\rangle=\frac{1}{\sqrt 2}(|uu\rangle+|dd\rangle)$ and $|T_3\rangle=\frac{1}{\sqrt 2}(|uu\rangle-|dd\rangle)$.
Let's change basis with a similarity matrix $P=(|T_3\rangle~|T_2\rangle~|T_1\rangle~|S\rangle)$.
In this new basis, $|S\rangle...|T_3\rangle$ are basis vectors and 
$$
A=\tau_z\sigma_{z,new basis} = 
\begin{pmatrix}
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 \\ 
0 & 0 & -1 & 0 \\ 
0 & 0 & 0 & -1
\end{pmatrix}
=\begin{pmatrix}
1 & 0\\
0 & -1
\end{pmatrix}
\bigotimes
\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
$$
$$
B=\tau_y\sigma_{y,new basis} = 
\begin{pmatrix}
1 & 0 & 0 & 0 \\ 
0 & -1 & 0 & 0 \\ 
0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & -1
\end{pmatrix}
=\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
\bigotimes
\begin{pmatrix}
1 & 0\\
0 & -1
\end{pmatrix}
$$
We consider the new basis vectors as product vectors isomorphic to single spins which can each be in states labeled $|+\rangle$ and $|-\rangle$ (so as not to confuse with $|u\rangle$ and $|d\rangle$) and we get that
$$
|S\rangle = |{--}\rangle,~~~~
|T_1\rangle = |{-+}\rangle,~~~~
|T_2\rangle = |{+-}\rangle,~~~~
|T_3\rangle = |{++}\rangle
$$
Since $A$ and $B$ are of the form of product operators, we can let them define a new subdivision of the full system. Each new subsystem no longer corresponds to an electron at a specific location, as in the original division. A and B can be thought to operate on one label each (A on the first + or -, B on the second).
With this new subdivision, each of $|S\rangle...|T_3\rangle$ are not entangled.
To conclude
Entanglement is in the eye of the beholder (4x4 operator, or subsystem division). Yes?
 A: I think I understand your question, but I don't understand Aaron Stevens's comments at all, which you claim to be a valid rephrasing, so it's possible that I'm not actually understanding your question correctly. With that caveat:
Your basic idea is right, but your statements aren't quite mathematically precise enough to be completely correct. (For one thing, you're using the words "entangled" and "pure" as if they were mutually exclusive, but they're not - the maximally entangled state that you describe is both entangled and pure.) Yes, whether a state has internal entanglement does indeed depend on how you factor the Hilbert space into subsystems.
But you're missing a key point, which is that the Hilbert spaces for a composite system is a tensor product of the individual systems' Hilbert spaces, not a direct sum. The Hilbert space $\mathcal{H}_{AB} = \{ |uu\rangle, |ud\rangle, |du\rangle, |dd\rangle \}$ for a two-spin system is the tensor product $\mathcal{H}_{AB} = \mathcal{H}_A \otimes \mathcal{H}_B$, where $\mathcal{H}_A$ and $\mathcal{H}_B$ are both isomorphic to the Hilbert space $\{ u, d \}$ for a single spin. So we can meaningfully talk about operator that only act on one subsystem. But the set of linear combinations of the $|S\rangle$ and $|T\rangle$ states forms the direct sum $\{|S\rangle\} \oplus \{|T\rangle\}$, so we can't think of the $|S\rangle$ and $|T\rangle$ states as subsystems that operators can act on independently.
Sometimes, a composite system's Hilbert space can be written as a tensor product in two inequivalent ways. This really does correspond to two different valid ways to divide the complete system into subsystems, and whether or not the subsystems are entangled can indeed depend on that division. (But this is not quite the same thing as basis dependence, because it turns out that the entanglement is independent of the basis one chooses for each subsystem. Once one chooses a division of the complete system into physical subsystems, then any change of basis within one subsystem will not affect the entanglement.)
We can't see this with your two-spin example, but we can see it if we consider a system of three spins $A$, $B$, and $C$, whose Hilbert space is $\mathcal{H}_A \otimes \mathcal{H}_B \otimes \mathcal{H}_C = \{ uuu, uud, udu, udd, duu, dud, ddu, ddd \}$. Consider the state
$$\frac{1}{\sqrt{2}} (|u_A d_B\rangle - |d_A u_B\rangle) \otimes |u_C\rangle = \frac{1}{\sqrt{2}}(|udu\rangle - |duu\rangle).$$
In this state the spins A and B are maximally entangled, but the spin C is not entangled with either of them. One person might only have experimental access to operators that act on either (a) the A and B spins or (b) the C spin. This person would naturally consider the A and B spins together as comprising a single subsystem, and the C spin as comprising a separate subsystem. They would therefore naturally factor the Hilbert space as $\mathcal{H} = \mathcal{H}_{AB} \otimes \mathcal{H}_C$, and say that the state is not entangled. They would not observe any unusual correlations between spins in "separate subsystems".
But someone else might have experimental access to a different set of operators, which can only act on either (a) the A spin, or (b) the B and C spins. This second person would naturally consider the A spin as comprising a single subsystem, and the B and C spins together as comprising a separate subsystem. They would therefore naturally factor the Hilbert space as $\mathcal{H} = \mathcal{H}_A \otimes \mathcal{H}_{BC}$, and say that the state is entangled (in fact, maximally entangled). They would observe perfect correlations between (what they describe as) "separate subsystems".
But again, once you specify a particular tensor factorization of your Hilbert space into fixed subsystems, then the entanglement between the subsystems is both basis- and observer-independent.
A: 
Entanglement is in the eye of the beholder (4×4 operator, or subsystem division). Yes?

Yes, but that is a pretty useless observation.
The formal definition of an entangled state of a bipartite quantum system with state space $\mathcal H = \mathcal H_A\otimes \mathcal H_B$ is as follows:


*

*a separable state is one whose density matrix can be separated as a sum of tensor products of individual density matrices, i.e. if $\rho\in \mathcal B(\mathcal H)$ is the density matrix of the system, $\rho$ is separable if and only if there exist density matrices $\rho_{A,i}\in \mathcal B(\mathcal H_A)$ and $\rho_{B,i}\in \mathcal B(\mathcal H_B)$ and weights $p_i\geq 0$ such that
$$
\rho = \sum_i p_i \rho_{A,i}\otimes \rho_{B,i}.
$$

*an entangled state is any state that is not separable.


For clarity, entanglement is an intrinsic property of the state, together with the partition of the state space into tensor factors. 
If you're willing to re-factorize your total state space into some other tensor-product factorization, then a state that's entangled in the $A$, $B$ bipartite scheme is indeed liable to be seen as separable in some alternative $A'$, $B'$ factorization. 
However, if you're able to re-factorize your total state space in such a way, then that tells you that your initial split into parties wasn't very meaningful to begin with. In real-world scenarios, we use entanglement as a relevant concept for bipartite systems where the tensor-product factorization of the state space (i.e. the splitting of the system into the two "parties" alluded to in "bipartite") is fixed from the context and cannot be changed easily. If you see it used in a context where that's not the case (ahem) then any conclusions drawn from the entanglement are correspondingly weakened.
One useful way to see this is by noting that the theory of entanglement is, very often, best thought of as a resource theory. Resource theories are great ways to analyze situations where you have one class of operations which is easy to implement but which might be insufficient to achieve some pre-specified goal. Other good examples are thermodynamics (where the operations are energy-conserving processes, and the resource is entropy) and gaussianity (where the operations are linear optical operations); in entanglement, the class of free operations is that of Local Operations and Classical Communication, generally abbreviated as LOCC, and it is obviously tied strictly to a splitting of the system into parties which can operate 'locally' and which can communicate classically.
Resource theories, of course, are only useful when the resource they describe is actually valuable, and when their restricted operations are in fact hard to implement: just as the study of thermodynamics is pretty useless if you have a magical black box that can inject and remove energy from any part of your system at your command, the study of entanglement is pretty meaningless if you have free access to non-LOCC unitary operations that cut across the A-to-B split.
That doesn't mean that you can't talk about entanglement in such a situation, like e.g. the spins of two electrons which are in bound states in the same atom or molecule, but if the re-factorization is physically possible in anything like a reasonable sense, then the conclusions that stem from the presence of the entanglement will be correspondingly trivialized. 
But more importantly, if you look at real-world usage, it is always of the form 

this system is entangled with that system. 

Under your re-factorization, the first part of that sentence to lose its meaning is not "entangled", it's "system".

(The answer below addresses a specific interpretation of v6 of the question, which was, frankly, much more interesting than the current version. I'm keeping it around because of that.)
What Susskind provides is known as an entanglement witness, and here you do get some amount of "eye of the beholder" behaviour. Generically, an entanglement witness is some operator $A$ such that its expectation value in state $\rho$, $\mathrm{Tr}(\rho A)$, will satisfy
$$
\mathrm{Tr}(\rho A) \geq 0 \qquad \forall\text{ separable }\rho,
$$
so that
$$
\mathrm{Tr}(\rho A) < 0 \implies \rho\text{ is entangled}.
$$
However, most entanglement witnesses are imperfect: that is, for any given entanglement witness $A$, there will typically be entangled states $\rho$ for which $\mathrm{Tr}(\rho A) \geq 0$, so that $A$ cannot detect the entanglement of that particular entangled state.
Nevertheless, for any given entangled state, there will always be at least one entanglement witness that can certify that it is entangled.
In other words, the definition of entanglement is independent of the operators used to detect its presence, but typically those operators will have a limited scope in which entangled states they can detect.
And if that makes it sound like entanglement is a tricky object to detect and characterize, then... yes, pretty much.
