There can't be any 'verification' if no transaction is processed. So any vendor is going to have to receive your payment first before doing any screening on the transaction itself.
You went online and made the payment yourself, it is not like we charged your card randomly, once we received the payment then we have enough elements to screen the transaction, we do contact every person either by e-mail or phone when a high risk transaction is received, to verify the information provided with the payment. Maybe you were not home when we called or you misplaced our e-mail, since I don't know what is your order number I can't give you any specific details on how we contacted you.
Now, once we reject an order we immediately refund the card as we rather process the refund ourselves than deal with a chargeback later on, if after 2 weeks you haven't seen the refund posted to your crad it is matter of your financial institution to make those funds available to you. By the sound of it, it is an international card and the time it takes to hit your card has nothing to do with the vendor. As we mentioned on that e-mail, your card was refunded at the same time the order was rejected, and not too much we can do after that.
Everybody knows how credit card fraud is growing pretty fast in this industry and vendors have to protect themselves one way or another. If your order/payment was rejected I am sure it was for a reason, but remember that you can make payments offline for new orders and that way we can setup a server account for you, we have clients all over the world that send money orders or wire transfers for new orders all the time.