The information is required by the issuing bank, so re the "no-name" gift cards - you have to check the requirements of the issuer. Some might require the card to be pre-registered for online usage, and at that time they'll require the address of the user to be used for authorizations.
Many merchants also compare the billing and the shipping addresses and don't allow them to be different (as a fraud prevention measure). Some credit cards allow storing additional addresses so that you could buy and ship to different addresses with such merchants.
The address and name info is used to authorize the purchase by the issuer. Together with the security code, the card number and the expiration - it is compared against the info on the account, and the authorization will not be given if there's a mismatch in any item.
Similarly with Paypal, except that Paypal doesn't forward this information to the actual merchant. It is Paypal that is charging your credit card, not the merchant. The merchant only gets the name and shipping address.
With POS purchases, the POS sends the information encoded on your credit card magnetic stripe/chip to the issuer for confirmation. It doesn't have your address there, but it does have your name, card number, expiration, and additional security information, that is then compared against your account. If there's a mismatch - the purchase won't be authorized. If the card is reported stolen, the POS will be notified and the shop owner might call the police (technically the shop owner is supposed to destroy such a card, but rarely they do as it is dangerous).