I'm not sure where you are.
Here where I live I can just go to Circle K's, and Walmart, and some grocery stores, Radio Shack,Best Buy, and Target.
I'm thinking you can pay online with a credit card as well.
I know it's a regional thing, but here in Michigan we have Meijer. They sell top up cards that are rechargeable. I just go into the store with my card, take it to the cashier, and make my payment. It shows up on my VM account instantly.
Yup Walgreen's has 'em as does 7-11 (at least the one by me does). One thing I definitely like about VM is the ability to pay 24/7 and have service back up in minutes without using my debit or credit card.