I don't know if it will work but try putting your address first in the address box then right after put your PO Box in the same box. Or try it the other way around PO Box then Address. I think the reasoning behind it is that the physical SIM card is shipped via FedEx and can't be shipped to PO Box. It would simplify it if Visible had a separate box for shipping and billing addresses.
Only other way around this would possible be using PayPal but you mentioned you don't have another online payment option. PayPal is free to use when paying, the only fees involved with using them is when you use the service to receive money such as selling something on and using them to get the money added to your PP account. I use them a lot for when I order things online that accept them.