Just bought an HTC Amaze 4G (T-Mobile) and paired my old ThinkOutside Stowaway keyboard to it, no problem. Unfortunately, the ThinkOutside driver is needed for a lot of customization and settings, but the "expensive" little folding keyboard was made thoughtfully to comply with basic Bluetooth HID profiles for basic typing. Here's how to pair:
The pairing process can be secure or insecure ... with the appropriate driver (which I had for my Nokia 6682 (Symbian)). For Androids and iPhones, you're doing a secure pairing. As mentioned, hold down CTRL, LEFT FN (blue) and RIGHT FN (green) keys until the Keyboard Status Light (green LED above "T") starts blinking once per second. It's now discoverable. Scan for devices on your mobile, and select "Pair with this" when the correctly named keyboard comes up. Put in a PIN of 1-9 digits (numerals only) and click OK. Holding the LEFT FN (blue) key to enable numerals on your keyboard, enter the same numbers, and (still holding LEFT FN) click Enter/OK/Select.
Normally, the Keyboard Status Light will blink slowly (once every four seconds), indicating it is connected and ready. If the light stops blinking, the keyboard has gone to sleep, just press the space bar or another key again. If the light glows red after opening, it means you need to replace the batteries.
If you didn't have a manual, you may not have known about how to enter the PIN into the keyboard ... understandable. But I suspect that HTC Sense is not the culprit ... it's an overlay on the Android OS, and the basic OS would likely have pretty robust HID input device capabilities.