I've been trying to use one, but I keep getting that screen that tells me I entered the info wrong or my bank is blocking it.

Steam and Paypal accept them, so I don't get why GOG doesn't. I've tried paying via paypal for gog, but it just takes me back to the same screen.

I have used them before, so not sure what's up. However, you can attach them to your PayPal account and use them that way. You only have to buy one -- after the money runs out it will just take it from your bank account. Hope this helps -- works lovely for me. :)
PS. Belated welcome to GOG!

I attached it to my Paypal and selected the Paypal option in the checkout, but after clicking Pay Now it takes me back to the processing problem page on GOG:

we're sorry, but your payment attempt has been declined; this could have happened for two reasons:

1. Some of the information entered in the form was incorrect; you can re-enter it 2 more times.

2. The transaction has been automatically blocked by your bank and we recommend contacting them for assistance. Please note that some banks block all overseas transactions by default, until the customer authorizes them.

Oh I see. That's very strange indeed.
Which card do you have?
I've used the Vanilla Mastercard Giftcard and Citizens Bank Visa Gift Card, both with no issue.
Are you sure you entered all information into PayPal correctly (CC number + expiry date)? And is your bank account connected to your PayPal account as well?

I'm having the same problem. I have no trouble using my Visa gift card on steam or other services, but it won't work on GOG. In fact, I used the same exact card to make a purchase on GOG a month ago, and it worked just fine, but now it won't work.

It's just one of those Visa "the ideal gift" cards you see at grocery stores that come in increments of like $15, $25, $50, and $100. Also nothing else is attached to the paypal account.