The MX-500 sends commands in a macro for a specified and non-customizable amount of time. The only thing I can think of is that your devices aren't receiving the code for long enough, however this isn't a common problem with the MX-500. Perhaps your original remotes' batteries are low and the MX-500 is learning the codes a bit "slow"?

One quick thing to test that I always do with the MX-500-850 - when you push a learned button on the MX-500, watch the transmit icon on the LCD. You should be able to flutter your finger on the button (ie rapid pushes) and the icon should mimic exactly what you're doing. if the icon seems to stay on for slightly longer than you hold your finger, or you're unable to see breaks in the icon when you perform very quick repeats, that's usually a sign of a bad/corrupt learn.

The MX-500-850 can be picky on learning; I usually have at least a 25% fail rate on every learning session (and yes, that does mean I occasonally end up learning some buttons 3 times).

And while your procedure sounds correct, whenever someone has learning issues I usually suggest trying other learning techniques (including normally incorrect ones) to see if anything works better.

You can find a list of these here [Link: remotecentral.com]