I just came across this thread after suffering the same problem. The only difference is that I am running Win 7 (although this should not be relevant since it is still supposed to be supported).
I previously used a WiFi keyboard with a dongle that worked fine, but I wanted to switch to Bluetooth to solve another problem, so I thought I would get a MS keyboard rather than a third party device since I figured it was sure to be completely compatible with their own OS.
I have also tried a number of the suggested solutions with no luck. So far I have tried the MS Surface keyboard and the MS Designer keyboard and mouse, in addition to Dell and Matias keyboards with identical results so I'm pretty sure it is not a problem with the devices (what are the chances of 4 keyboards from 3 independent manufacturers having the identical problem). The only common component is Windows.
Given the number of people who have appeared on this thread, it is hard to believe that MS have not come across this issue and put some effort into fixing it. As someone else said, I would also put money on it being a sleep problem. I did come across a setting that said "Allow the computer to turn off this device to save power", but it was not selected.
I don't really have an issue with the fact that such a problem might exist (all software has bugs), but what did surprise me is that this thread seems to be about 2 years old and still going. Not only that, but while searching I also came across other posts that were even older (in some cases more than 6 years), and still no hint of a solution from MS.
I did find a solution that works for me, but it doesn't involve MS at all, so I can't contribute anything more useful for those glued to Windows. Sorry, guys.