The scenario with VirtueMart is perfect for the web, all the balance is done in Virtuemart. And you have nothing to do.
For the in-store part, this is more difficult, (maybe), because the only thing you need to do if someone come in-store with the gift card, is open Virtue mart and search the number in the coupons section and you have the card balance there.
You need a computer with internet in store and teach the staff how to use it.
Also if you have a current system in-store for plastic gift card, It's possible to do a bridge between Virtue mart and the in-store system, it need work but I already did it for a customer, any php developer could do the trick. ( IF THE IN-STORE SYSTEM ALLOW IT)