iMac USB Ports Stopped Working
Hinted by similar discussions in related forums, I figure it's bad contacts.
I fixed my issue by gently squeezing the keyboard USB to make it tighter. Be careful not to break it though. Just a gentle squeeze, so that it's about 0.5-1mm tighter should be all that's needed.

This would explain why new keyboards work fine for a while and why extension cords only help for a while only as well.