Hi!
It looks like a problem with the MIDI driver. I have Evolution UC33, UC16 and MK249C2 (M-Audio bought evolution) and occassionally have the same problem. It not only happens to Live, I have the same problem with other midi programs.
My suggestion: I don't have any good suggestion. Cheap suggestions:
1) Use Microsoft driver instead of MAudio/Evolution driver. Yes, Microsoft drivers do suck a lot, they are not multiclient and stuff, but this problem is less frequent.
2) Mail-Bomb M-Audio asking for a driver update. The actual driver is pretty old and I don't know if they plan to upgrade it.