This has to be carrier-dependent? I have people tell me my vm is full (and I think my phone has done the same).
So I’ll delete some (blocked callers can leave messages too) and it frees up.
But oddly, some times someone will say it’s full and after that, someone else leaves a long message.
I’m on Verizon.