Strange Wired Mac Keyboard behavior
I ended up carefully removing all the key caps (like shown here http://www.youtube.com/watch?v=G_Cue2IlXIg) and cleaning up the dust/dirt that accumulated over the past two years. I guess it messed with the electronic contacts.