We traced the problem to the interrupt handler that handled data coming from the host. The first thing that ISR does is to validate the "dance" that the host does to indicate it has some data it would like to send us. The host tells us it wants to send some data by holding its clock line down for a while (supposedly around 100usec), then lowers its data line, then allows the clock line back up. This is called request-to-send.

Our ISR was apparently not doing a good job of validating that. We fixed it by increasing the amount of time (loops) that we made sure the host was holding down its clock line and increased the amount of time allows for the next two events to happen.

We had figured that the proxying was working correctly, so the PC must be doing something strange that wasn't a relayable command. But in fact, the relaying wasn't working right. The keyboard wasn't acknowledging the PC's commands because it simply wasn't seeing them.

Thanks to everyone for help and suggestions.