Can Microsoft trace previously pirated license from Computer HDD.
Yes. It is possible to redo a format to some extent (with "testdisk"). But doing so would probably be far more costly then letting it slip since they need to get there hands on your system (and that probably requires a court order in most countries).
Mind you: if you bought the system from a store that is a chance you already paid for windows (prior to windows 8 you would have a sticker on the system with the serial; windows 8 seems to store the serial in bios(?)).
What is the best HDD formatting method/software so Microsoft will not trace license from HDD. ?
Best method? Throw away the harddisc and get a brand new one.
Technically you can use tools to zero-fill your disc several times to make sure all was erased (since formatting most times does not erase the disc but removes just the partition table (short version ;) )) but a new harddisc is the least time consuming method.