We have seen a variety of MIDI problems with customers using Cubase 4 (or any recent Steinberg DAW) that have all been fixed with the same solution. These problems range from MIDI tracks drifting out of sync with audio tracks to Cubase not allowing MIDI tracks to be recorded to more than once.

The solution is to enable the Windows time stamp feature in Cubase. This can be found by going to:

Devices > Device Setup > MIDI Port Setup.

Here, make sure that the box for "Use System Timestamp for 'Windows MIDI' Inputs" is selected with a checkmark.
You should also make sure that the MIDI input and output ports in this window are also "activated" in the choices above.