Hmmm... the only other thing I could suggest is to take advantage of the warranty on the keyboard, if there is any left. It seems to be a hardware problem to me, but there's one last test you should do:
Create a new user, and try and pair the keyboard under the new user account.
Ah, one other thing that you may want to try is to turn off the computer, keyboard, and mouse and leave them off for an hour or so (overnight if possible), then try pairing again. Perhaps that'll "reset" something enough to make the keyboard pair.