So you'd be happy with one supported for Linux, not for N800? That's not what you'd initially said; you might catch one of those.

So far, I have not heard of one BT keyboard claiming HID compliance that doesn't work, so my idealism seems to match reality. There are problems, but all the problems I've seen involve either non-HID keyboards, or problems with the N800's software (which affect any keyboard).

I'm not sure what you mean by You've got two issues in this that make it very hard to see a similarity:

1. There's a huge difference between saying an OS will work on any computer and saying that it's 100% feature compatible (by which I understand you to mean that all integrated and bundled peripherals may be exercised from that OS).
2. You don't reference any standard that the computer is stated by the manufacturer to comply to, and that Linux is also stated to comply to. If there is such a standard, then you'd expect all functionality required by the standard to work; if not, then it should not be surprising that some stuff doesn't. In reality, there are a good number of standards regarding BIOS, PCI, USB, etc., that the PC complies with, and Linux supports them. The troubles that are run into with some computers are generally from proprietary devices with functionality not defined by any standard.