A proper deleting of the partitions and fresh install would be best and the only 100% guarantee that it would be clean
But you have to make sure to have the windows setup delete the partitions, that way if there is a boot sector virus it will get wiped as well, a format wont cut it.
Shane