It's actually an interesting problem you raise, so let me try to expand a bit on my comment.
In general, the program for “showing that [first-order] perturbation theory (PT) works” is the following:
- Solve the perturbed problem exactly, yielding solutions $H\psi_n = E_n\psi_n$.
- Differentiate the results by the perturbation parameter, i.e. compute $dE_n/dv$ and $d\psi_n(x)/dv$.
- Compare this to the PT results $E_n^{(1)}$ and $\psi_n^{(1)}(x)$.
In the present case, this will not be possible analytically. Write an Ansatz for the full solution, split in two regions, (L) $V(x)=v$, and (R) $V(x)=0$. As in the regular infinite potential well, for each region you can eliminate one of the linearly independent solutions by the boundary conditions $\psi_L(0) = \psi_R(a) = 0$.
You are left with three parameters (an “amplitude” for each region, and the energy) and three relations to fix them ($\psi_R(a/2) = \psi_L(a/2)$, $\psi'_R(a/2) = \psi'_L(a/2)$, $\int\!dx\,\psi(x) = 1$). Simple enough in principle, but not analytically solvable in this case because the energy is given by an implicit transcendental equation.
The reason I say your problem is interesting is that, as you increase $v$, it will change the character of the lower-lying states. In the unperturbed case, all states are “oscillatory”, albeit cut off at the edges. In the perturbed case, this will still be true on the right side, but once $v$ is big enough, you will get states that decay exponentially on the left. A sensible guess would be that PT breaks down for these states.
As for $V_{nm} = \langle\phi_n|V|\phi_m\rangle$ and orthogonality: The $\phi$ are even/odd functions with respect to the well center. Split the integral $\langle\phi_n|\phi_m\rangle = \int_0^a\!dx\phi_n\phi_m = L + R$ into two parts corresponding to left and right side. As you say, $L + R = 0$; and $V_{nm} = vL$. If $n$ and $m$ have the same parity, $L=R$ and so $V_{nm} = 0$; but if the parity is different, $L=-R$ and $V_{nm}$ is non-zero.