My midi sustain pedal has a reverse polarity switch which would have this effect. Maybe you have a loose connection on it.
To see if it is a hardware problem you could unplug the offending pedal and use the shift key while you have the on-screen keyboard loaded up. If that behaves as expected I'd be looking into replacing or repairing the pedal.
This Is My Song
@pushedbutton on twitter
I live in Lancashire, England.