I used different methods. Generally, I just took a handful of tubes and rinsed them with acetone. Separated out the clean from the less than clean. Let them dry and separate them again. Then I'd try rinsing the dirty ones again with different solvents, heating, etc. or use an NMR tube cleaner similar to what Stewie suggested.
It depended on what I wanted the tube for. If I was just checking a reaction, I didn't knock myself out with handling individual tubes. I can add acetone to about 50 tubes, dump and repeat pretty quickly. If I wanted a really clean tube, I just used a new one. (How else can you acquire a stock of dirty NMR tubes?)