Strange, I believe I tried that after receiving a bunch of gift cards for Christmas -- I even tried entering in the exact title that's below the CC number on the card, but had no luck.
That's a different issue, namely address verification. You can sometimes log-in to the issuers site or call and give an address (can be fake, just needs to be something you remember) and then use that address on whatever online form you're trying to use. It will pass AVS and you're good to go.
http://www.americanexpress.com/us/content/prepaid/gift-cards... http://usa.visa.com/personal/cards/prepaid/gift_card_faq.htm...