Say $Z$ is a nonnegative random variable. First we can describe the integer component of $Z$ as $\sum_{n\in\mathbb{N}} I_{n\leq Z}$. Since $Z$ is always greater or equal to its integer component we have
$$ \begin{split} \mathbb{E}[Z] & \geq \mathbb{E}\left[\sum_{n\in\mathbb{N}} I_{n\leq Z}\right]\\ & = \sum_{n\in\mathbb{N}}\mathbb{E}\left[I_{n\leq Z}\right]\\ & = \sum_{n\in\mathbb{N}}\mathbb{P}\left(Z\geq n\right). \end{split} $$
On the other hand we can also deduce the following.
$$ \begin{split} \mathbb{E}[Z] & = \int_\Omega Z\,d\mathbb{P}\\ & = \int_\Omega \int_{x=0}^Z dx\,d\mathbb{P}\\ & = \int_\Omega \int_{\mathbb{R}^+} I_{[0, Z]}\,dx\,d\mathbb{P}\\ & = \int_{\mathbb{R}^+} \int_\Omega I_{[0, Z]}\,d\mathbb{P}\,dx\\ & = \int_{\mathbb{R^+}}\mathbb{P}\left(Z \geq x\right)\,dx \end{split} $$
These results I've seen in the literature, so I don't think I'm off so far. But now use the fact that $\mathbb{P}\left(Z \geq x \right)$ is a decreasing function of $x$ to write
$$ \begin{split} \mathbb{E}[Z] & = \int_{\mathbb{R^+}}\mathbb{P}\left(Z \geq x\right)\,dx\\ & = \sum_{n\in\mathbb{N}}\int_{x=n}^{n+1}\mathbb{P}\left(Z \geq x\right)\,dx\\ & \leq \sum_{n\in\mathbb{N}}\mathbb{P}\left(Z \geq n\right). \end{split} $$
Finally, putting the first and last result together we arrive at
$$ \mathbb{E}[Z] = \sum_{n\in\mathbb{N}}\mathbb{P}\left(Z \geq n\right). $$
I'm a little perplexed that this result would hold for arbitrary nonnegative random variables. Is it actually correct?
You're right to be perplexed. This would seem to imply that $E(\lfloor Z \rfloor) = E(Z) $ for all non-negative random variables. Say $Z$ is an exponential random variable. Then we have $$ \int_0^\infty P(Z\ge x) dx = \int_0^\infty e^{-\lambda x}dx = \frac{1}{\lambda}=E(Z)$$ as promised. But we have $$ \sum_{n=0}^\infty P(Z\ge n) = \sum_{n=0}^\infty e^{-\lambda n } = \frac{1}{1-e^{-\lambda}}$$ which is generally larger than $1/\lambda.$
So in fact your second inequality $$ E(Z) \le \sum_{n=0}^\infty P(Z\ge n)$$ seems to be the correct one.
What was wrong with the first one? After all, it came from the seemingly bulletproof argument that $$\lfloor Z\rfloor=\sum_{n=0}^\infty 1(Z \ge n).$$ Except, wait... it's not. We have $$ 1 = \lfloor 1.1 \rfloor \ne 1+ 1 = 2.$$ This is overcounting by one. So in fact your first inequality should be $$E(Z) \ge -1+\sum_{n=0}^\infty P(Z\ge n).$$
This, perhaps more than anything, underscores the importance of never writing $$ \sum_{n\in \mathbb N} f(n)$$ and always writing $ \sum_{n=0}^\infty f(n)$ or $ \sum_{n=1}^\infty f(n),$ whichever is appropriate.