I encountered the same problem, that all other shortcuts with WinKey seemed to work perfectly fine, except for WinKey+R.
Symptoms
WinKey+R sometimes (rarely) worked on the the first try, sometimes after the 2nd or 3rd try, and sometimes it did not work at all; except when first focusing the Windows taskbar.Cause
This occurred immediately after installing Windows 10 (more precisely upgrading from Windows 7 to 10). So, installing Windows 10 was most probably the cause (on my system) for this is.
SolutionFor me, uninstallingAdobe Flash
did solve this problem
[EDIT] minha "solução" parece ter sido um golpe de sorte: ela pareceu funcionar por cerca de uma semana, depois voltou ao problema antigo ... então eu ainda não tenho ideia do que causa esse problema
[EDIT 2] esse problema foi resolvido / não ocorre mais desde a atualização para o Windows 10 ver. 1607