Why does induction with big-O lead to paradoxes?
You have to carry around the big-O constant. Suppose that we are trying to prove that $T(n) \leq Cn$. In the inductive step, we have
$$ T(n) \leq 3C\lfloor n/3 \rfloor + 2n \leq (C+2)n. $$
So we are not able to maintain the constant $C$. Let's have another go, with $T(n) \leq C_nn$. The argument above shows that we can put $C_n = C_{\lfloor n/3 \rfloor} + 2$, and so $C_n = O(\log n)$ works, and we get the correct asymptotics $O(n\log n)$. (To know that this is tight, we would also need a lower bound, proved in much the same way, with some minor technicalities stemming from the floor.)