Problem was largely due to a bug introduced in wxGTK 2.6.0 (and likely late 2.5.x).
A nasty work-around has been added in VLC that fixes this problem (r11031/11032).
There are still a few cases where the hotkeys won't work though when you start VLC... I'm not sure why, it could be the embedded vout screwing the focus somehow. To investigate further.
Pretty much all availeble keys work under windows, a few keys havent been ported to the directX vout, but i tihnk its only 1-3 that remains, under wxwin all keys, as far a si know, works.
I would sugest splitting this up between linux and windows and specifying more specific what issues remain.
Something here that might be related: Ctrl-+ seeks 1 min forward instead of increasing the volume (Ctrl-- works as expected, I don't know about other hotkeys). This only happens when the video is embed in the WX interface (go fullscreen or disable embed video and everything works fine). Using the current trunk on Debian Sarge (wxgtk2.5).