1) First, why are powers of linear factors repeated?
For example, $(x+1)^2$ gets $\frac{A}{(x+1)}$ and $\frac{B}{(x+1)^2}$
2) Why does a quad factor like $x^2+1$ get a term $\frac{Cx+d}{x^2+1}$
Looking for an example that shows WHY you need a linear term above the quadratic, and WHY you need to repeat the factors.
Here are some trivial counterexamples that illustrate why we must consider terms of the given form:
Consider the rational expression $$\frac{1}{x^2 (x + 1)} .$$ If we did not require terms with lower powers in the denominator, applying partial fractions to this expression would give entail solving $$\frac{1}{x^2 (x + 1)} = \frac{A}{x^2} + \frac{B}{x + 1}$$ for some constant $A$. Cross-multiplying gives $1 = A(x + 1) + B x^2$, and comparing like coefficients yields a contradiction, and hence there is no such decomposition as written.
Similarly, consider the rational expression $$\frac{x}{x^2 + 1} .$$ If we did not require a linear term in the numerator of expressions with irreducible quadratics in the denominator, applying partial fractions to this expression would entail solving $$\frac{x}{x^2 + 1} = \frac{A}{x^2 + 1} .$$ Again, there is no solution $A$.
Edit In the handwritten computations in the edit to the original question, the computations in the candidate decomposition with only two terms is incorrect: Writing $$\frac{1}{(x - 1) (x + 1)^2} = \frac{A}{x - 1} + \frac{B}{(x + 1)^2}$$ and cross-multiplying gives $$1 = A(x + 1)^2 + B(x - 1) = A x^2 + (2 A + B) x + (A - B) .$$ Then, comparing like coefficients gives the system $$ \left\{\begin{array}{rcl} A &=& 0\\ 2 A + B &=& 0\\ A - B &=& 1 \end{array}\right. $$ but this system has no solution, so yet again there is no such decomposition. (One can verify that something has gone wrong in the handwritten solution by combining the expression into a single ratio of polynomials.)