I guess you are right... :)

It seems to me that this indeed fails quite often.

Let $d=\mathrm{codim}_XZ$ and $P=f^{-1}Z\subseteq \widetilde X$ the exceptional divisor. By the assumptions $P\to Z$ is a $\mathbb P^{d-1}$-bundle.

First note that as long as $d\leq 2$, then the statement is probably true for the simple reason that if $V\neq X$, then $\dim (V\cap Z)\leq \dim V-1$ and hence
the largest dimensional part of the pull-back of the Segre class $s(V\cap Z, V)$ has dimension at most $\dim V$ and hence that's the only component that makes a meaningful appearance in the formula for $f^*[V]$.

So, let's go to $d=3$. In this case $P\to Z$ is a $\mathbb P^{2}$-bundle.
Now let $V\subseteq X$ be a surface such that $C=V\cap Z\subseteq V$ is a Cartier divisor in $V$. Then the Segre class in question is
$$
s(C,V)=[C]-[C]^2.
$$
Since we have a nice blow up, the "mysterious" *excess normal bundle* is just the relative tangent bundle $T_{P/Z}$, but this actually doesn't really matter, all we need is that there is a short exact sequence,
$$
0\to \mathscr O_P(-1) \to f^*N \to E\to 0,
$$
where $N=N_{Z/X}$ is the normal bundle of $Z$ in $X$.

So we need the class $\left(c(E)\cdot_P f^*([C]-[C]^2)\right)_2$.

Observe that
$f^*[C]$ has dimension $3$ and
$f^*[C]^2=f^*([C]\cdot_V[C])$ has dimension $2$, so we need to intersect the first with $c_1(E)=c_1(f^*N)-c_1(\mathscr O_P(-1) )$ and the second with $c_0(E)=1$.
Using that
$$
c_1(f^*N)\cdot_P f^*[C]= f^*(c_1(N)\cdot_Z [C]),
$$
we get that
$$
\left(c(E)\cdot_P f^*([C]-[C]^2)\right)_2=
f^*(c_1(N)\cdot_Z [C]-[C]^2)+
c_1(\mathscr O_P(1))\cdot_P f^*[C].
$$
So, it seems that if the intersection $C=V\cap Z$ is such that

- $C^2>0$ on $V$, and
- $c_1(N)\cdot_Z C<0$ on $Z$,

then the above class will not be effective. Note that these choices make the $f^*$ part of the class negative effective while the other class is "horizontal", so it is unlikely to cancel the "vertical" classes, but in any case one can probably play around with $V$ and $Z$ to make this more precise.

It seems that if the codimension of $Z$ is even higher and the intersection $V\cap Z$ is still large in $V$, then there is even more that can go wrong.