I've tried looking for it, guess what I found.
>Codes are region locked, but I think they are locked to the location you are, not the region of your 3DS.
>In other words: Store > 3DS Region.
From here,
>Actually there's a good chance the code won't work for you then. The codes seem to be region locked.
From here,
>...so please don’t enter if you are not in this region and/or it wouldn’t work for you.
From here as well,
>Unfortunately, the codes are region locked I think, so I am afraid it won't work. A UK code will not work for a US game card.
And lastly, from here.
TL;DR There's a high chance that the codes are in fact, locked to the region from where they were bought from.
So,
Good news: It's not the game card's or the DS' fault, both are completely fine and dandy.
Bad news: The Gengar code is not gonna work :/
Hope I helped!