How quickly must a move be completed? I was playing in a tournament once, during a sequence of captures, my opponent could recapture my Knight about 4 different ways. He just removed it and carried on thinking.

What should I have done?
The mere act of touching one of your pieces obligates your opponent to capture it (if legally permitted) on his current move (at least according to USCF standards), unless he explicitly declares his intent to adjust the piece beforehand. Assuming the clock continued running on your opponent's time and he did eventually choose how to capture the knight, I suspect that what he did would be considered legal (though somewhat unorthodox). However, if he didn't end up properly capturing the piece after touching it and before punching his clock, you would've unquestionably been justified in complaining to the official arbiter.