I remember reading that gifts are region locked. (They cant be redeemed.)
Correction: Steam gifts purchased from low-price territories can't be redeemed everywhere. A UK-bought Steam gift can be redeemed everywhere just fine, but a Russian-bought Steam gift can only be redeemed in Russia and a few other territories (Ukraine? Countries belonging in the Commonwealth of Independent States?)
However some games are not. For example I own Duke Nukem Forever (RUS) on Steam. Now you can't get it from the Steam store directly, but you can redeem the code for it fine and download/play it fine even if your not in Russia.
There are a few other region free games, but as I said above even if you get them sent as gifts, I dont think you can redeem them. As im almost 100% sure that all gifts for region spec games are region locked.
Keys bought outside Steam don't necessarily work the same as gifts that are bought from Steam itself. They may or may not have regional restrictions.