Obviously if the flight is completely sold-out you won't be able to add your companion to it. But one time WN refused to allow me to add a companion when BS and AT fares were still available. "There are no seats for companions left," a Southwest phone agent explained to me.
"You're saying there's now a special quota on companions? Where's that documented?" I asked.
"It's not documented externally. But there's a special fare category needed for companions, and that category's all sold out on your flight. The military rate is in the same category. We can't sell more military fares on that flight, either."
In retrospect I'm not sure if I stumbled across some arcane WN policy or just a very... misinformed... agent. I figured I'd HUCA the next day, though by then I'd chosen to change my own flight, anyway, and booking a companion seat on it was no problem.