Which one should I choose: a research scientist at Google or a researcher at Microsoft Research Redmond?

MSR tends to be more academic. The primary product of research at Microsoft is publication, and researchers at MSR are very much involved with the broader academic community (e.g., they have many academic visitors, they are involved with many conferences, etc.). Publications are an important factor in evaluating researchers, and researchers are motivated to publish. At Google, on the other hand, publishing is not valued as much (not discouraged as another answer implied, but not explicitly encouraged either). Publications are only a secondary factor in evaluating researchers, and as a result (given how busy researchers are with their projects) the rate of publication per researcher is far lower at Google.