I am currently experiencing the exact same dilemma on my desktop and notebook. I am also using Steam on Arch x86_64 with the Steam Mobile Authenticator. First I thought some settings were wrong but then I stumbled upon this. A friend also has the same problem.
Just for confirmation...
Nothing extracted yet.
DISCLAIMER: NOT SURE IF THIS IS A BUG FOR ONLY LINUX OR NOT
I have two Linux computers (Arch Linux x86_64). When I log into one computer, I type a Steam Guard code like normal (via Android application). The next computer I log into, I type in another Steam Guard code for that. If I then try to log back into the first computer, I have to type another code, but if I instead relogged into the second computer without touching the first, I don't have to type in a code.
Seems strange that this occurrs...