Wireless keyboard/mouse problem with iMac during start-up
At first I thought that maybe you had a firmware password enabled, but some of the stuff you mentioned doesn't line up (being able to reset the PRAM, and choose a startup disk at least some of the time).

Have you checked to make sure that you've got all the updates? Specifically, the keyboard firmware updates?