Good point, you can special order just about anything. That's the point - you pay up front on a sale guaranteed to go through, and have expressed the commitment.
Unlike the other guns in the rack, which are there on speculation - highly researched and measured. They'll sell, too. But with every square inch of space dedicated to making a profit and having turnover, it's obvious that the AK doesn't have the draw some think it should.
If it did, then it would be on the shelf making money. Political correctness won't really keep it off the shelf, check the contraceptives aisle, or the books and magazine rack.
As for "Walmart won't sell terrorist weapons," I guess that's the informed view of one of their typical customers.