Depends on what was on the machine
If it was one of the common spy ware progs that is easily removed by even Ad-aware, I am comfortable with thinking it was removed completely.
With Vundo and the wonderful Anti virus 2009 (or any of the other versions) I will re image.
All of my users are in Remote locations so I cannot have them sending the laptop in multiple times.