I'm working on a neighbors 2002 Lexus RX300 by replacing all door lock actuators. While working on the drivers' door I accidentally had the key on while I plugged in the door switch module to test the window had full travel. Doing so sent the locks into a lock, unlock cycle that wiped the remote memory.
I was having the same problem programming the remotes as mentioned in this thread. I could get through the whole procedure, but they refused to work when I finished.
This is what I finally did, but I'm not sure which of these actions was the trick.

I inserted one of the keys in the drivers' door to lock and unlock all doors. I also found that by turning the key twice in the unlock position that all windows and sunroof would open. I opened and closed the windows with the key twice. I then tried the programming once again, but this time I used the "turn-key to ON twice" at the end of the steps to erase past remote from the memory. (I had tried this trick at least once during my first 10 attempts to get the keys programmed) I was successful in programming two remotes in two separate procedures. (meaning I didn't program both at once since I wasn't sure this time it would work)