Perhaps there is something relating odd ordered partitions with even ordered partitions?
There is indeed. Let's try to construct an involution $T_n$, mapping odd ordered partitions of $n$-element set to even and vice versa:
if partition has part $\{n\}$, move $n$ into previous part; otherwise move $n$ into new separate part.
Example: $(\{1,2\},\{\mathbf{5}\},\{3,4\})\leftrightarrow(\{1,2,\mathbf{5}\},\{3,4\})$.
This involution is not defined on partitions of the form $(\{n\},\ldots)$, but for these partitions one can use previous involution $T_{n-1}$ and so on.
Example: $(\{5\},\{4\},\{1,2\},\{\mathbf{3}\})\leftrightarrow(\{5\},\{4\},\{1,2,\mathbf{3}\})$.
In the end only partition without pair will be $(\{n\},\{n-1\},\ldots,\{1\})$. So our (recursively defined) involution gives a bijective proof of $\sum_{\text{k is even}}k!{n \brace k}=\sum_{\text{k is odd}}k!{n \brace k}\pm1$ (cf. 1, 2).
Upd. As for the second identity, the involution $T_n$ is already defined on all cyclically ordered partitions, so $\sum_{\text{k is even}}(k-1)!{n \brace k}=\sum_{\text{k is odd}}(k-1)!{n \brace k}$.
P.S. I can't resist adding that $k!{n \brace k}$ is the number of $(n-k)$-dimensional faces of an $n$-dimensional convex polytope, permutohedron (the convex hull of all vectors formed by permuting the coordinates of the vector $(0,1,2,\ldots,n)$). So $\sum(-1)^{n-k}k!{n \brace k}=1$ since it's the Euler characteristic of a convex polytope.
The generating function of $\sum_{r,s\geq 1, \ rs\le n}p(n-rs)$
is
$$\sum_{n=0}^\infty p(n)q^n\sum_{r=1}^\infty\frac{q^r}{1-q^r}
=\sum_{r=1}^\infty\frac{q^r}{1-q^r}
\prod_{j=1}^\infty\frac{1}{1-q^j}.\tag{1}$$
The $r$-th term in $(1)$ is
$$\frac{q^r}{(1-q^r)^2}\prod_{j\ne r}\frac{1}{1-q^j}
=\sum_{t=1}^\infty tq^{tr}\prod_{j\ne r}\frac{1}{1-q^j}.$$
This equals
$$\sum_{\lambda\in\mathcal{P}}a_{r}(\lambda)q^{n_\lambda}$$
where $\mathcal{P}$ is the set of all partitions, $n_\lambda$
is the number partitioned by $\lambda$, and $a_r(\lambda)$ is the
multiplicity of $r$ as a part of $\lambda$. Then $(1)$ is
$$\sum_{\lambda\in\mathcal{P}}A(\lambda)q^{n_\lambda}$$
where $A(\lambda)$ is the number of parts of $\lambda$. But
that is also
$$\sum_{k=1}^\infty k\sum_{n=k}^\infty
p(n,k)q^n=\sum_{n=0}^\infty\sum_{k=1}^n kp(n,k)q^n$$
which gives the desired result.
Best Answer
These are recurrence relations for different problems. You could not simultaneously have $$P(n,k) = P(n-1,k-1) + P(n-k, k)$$ (your second identity) and $$P(n,k) = P(n-k,k-1) + P(n-k, k)$$ (the identity Euler discovered) because that would imply $P(n-1,k-1) = P(n-k,k-1)$.
I suspect that Euler's identity is for the problem of partitioning $n$ into distinct parts. If we define $D(n,k)$ to be the number of ways to partition $n$ into $k$ parts all of different sizes, allowing $10 = 5+3+2$ but not $10 = 4+3+3$, then we have the recursion $$D(n,k) = D(n-k,k-1) + D(n-k,k).$$ The argument is by the following two cases: