I think you vastly underestimate both the buying power and brand loyalty shown by people who choose to shop at any retailer, especially discount ones like Walmart.
Cashiers will almost assuredly offer a Walmart branded MasterCard or Amex if they were trying to buy with visa.
Bingo- Walmart has both eliminated visas Costs and developed a new revenue stream. And I imagine their quants know how many of their visa customers have alternate credit cards or debit capabilities.