Does RSA work for any message M? I decided to read the original RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystem because of a question I had about RSA (which is not the question I'm about to ask, but may be a question on here at some time) and came across something I had never seen before in any textbook description of RSA (Note: this comes from the beginning of Section VI of the paper).

for any integer (message) $M$ which is relatively prime to $n$,
$M^{\phi(n)} \equiv 1\pmod{n}$

The part I don't recall ever hearing in class, or coming across in a text book, or seeing in any description of RSA I've ever read is that $M$ and $n$ must be relatively prime.
So, I decided to play around with a toy example of RSA to see what would happen. I use $p=13$, $q=31$, $e=7$ and $M=2p=26$ (for completeness: $d=103$, $\phi(n)=360$, $n=403$).
I observed the following using my toy instance of RSA: $M^e\equiv M\pmod{n}$, $M^e\equiv 0\pmod{p}$ and $M^e\equiv M\pmod{q}$.
Do these equivalences hold for all $M,p,q$ when $M$ and $n$ are not relatively prime? How would I prove this? What is the real-world effect of this?
Yes, (textbook) RSA works for any message $M \in \{0\dots n-1\}$, in the sense that the decryption procedure recovers the original message; that is $\left((M^e\bmod n)^d\bmod n\right)=M$. For this to hold, we need to assume $p\ne q$, a requirement not formally stated in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, but true with overwhelming odds given the method suggested to generate $p$ and $q$, and always true when following the recommendation given that $p$ and $q$ differ in length by a few digits.
An easy proof is to consider $Z=\left(M^e\right )^d-M$; show $Z\equiv 0\pmod p$ and $Z\equiv 0\pmod{q}$, by using Fermat's Little Theorem and the assumed relation between $e,d,p,q$ (see detailed proof below); then, since $p$ and $q$ are distinct and prime, and divide $Z$, their product $n$ divides $Z$; thus $Z\equiv 0\pmod{n}$. Q.E.D., thanks K.G.
Note: in general, $M^e\equiv M\pmod{n}$ does not hold.
Note: if $p=q$, the cryptosystem is totally unsafe. Independently, those rare $M$ that are a non-zero multiple of $p$ are modified by encryption followed by decryption.

Detailed proof (following another question): we want to show that $Z=\left(M^e\right )^d-M$ verifies $Z\equiv0\pmod p$, that is $\left(M^e\right )^d-M\equiv 0\pmod p$, that is $M^{e\cdot d}\equiv M\pmod p$. Since $d$ and $e$ are integers greater than $1$, this holds if $M\equiv0\pmod p$; it remains to prove it only when $M\not\equiv0\pmod p$, which we assume in the following.
The original RSA article constructs $d$ and $e$ with $e\cdot d\equiv1\pmod{\phi(n)}$, where $\phi$ is the Euler totient, also noted $\varphi$; while modern expositions of RSA, including PKCS#1 of RSA Security, often use $e\cdot d\equiv1\pmod{\lambda(n)}$, where $\lambda$ is the Carmichael function. We hypothesized that $p$ and $q$ are distinct primes, thus $\phi(n)=(p-1)\cdot(q-1)$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. Thus $p-1$ divides $\phi(n)$ and $\lambda(n)$, and for either construction of $d$ and $e$ it holds that $e\cdot d\equiv1\pmod{(p-1)}$. Since $e$ and $d$ are integers greater than $1$, it therefore exists a positive integer $k$ with $e\cdot d=k\cdot(p-1)+1$.
We can thus write $M^{e\cdot d}$ as $M^{k\cdot(p-1)+1}=\left(M^{p-1}\right)^k\cdot M$. By Fermat's Little Therorem, since $p$ is prime and $M\not\equiv0\pmod p$, it holds that $M^{p-1}\equiv1\pmod p$. It follows that $M^{e\cdot d}\equiv M\pmod p$.

Addition following comment: RSA is sometimes presented in $\Bbb{Z}_n^*$ because:

The early version of Rivest, Shamir, and Adleman's paper did.
As pointed there, that's not a serious practical limitation because so few messages are excluded.
That removes any hypothesis on $n$ and thus makes the proof simpler; by contrast, we need a square-free $n$ in order for RSA to work in $\Bbb{Z}_n$.