Virgin does not allow non-Virgin handsets on their network. If the phone's ESN does not match that of a Virgin branded phone, it won't be allowed on the network.
Is the GS3 a GSM or CDMA version of the phone? Typically, phones that are sold unlocked are GSM phones -- CDMA phones must be programmed to work on a network whereas GSM phones it is typically a matter of swapping in a SIM card. If the phone is a GSM then your best bet would be T-Mobile (either prepaid or Value plan) or Straight Talk (or similar GSM MVNO).