solar_dome, currently there's a bug in the gift redeeming system that prevents user from completing the redeeming process for a game that was removed from the GOG.com catalogue. It will be fixed in a minor update coming soon to our live servers. In the meantime, if you have this problem, please drop our support an email and we will fix that for you manually asap.
PS: Yes, this is the bug, because the game is sold when user purchases the gift certificate and redeeming process is only a matter of binding a previously purchased game with some account. Redeeming should not be affected by the fact that game is no longer available for purchase (permanently or temporarily).