Formatting...is probably the best common effort that can be made...to remove malware.
IMO, in today's world, it's hard to say that anything positively eliminates malware...routers can become infected and they are connection-interface devices, so I would not assume that formatting the hard drive eliminates the nauseous aspects of malware.
Just a user opinion in 2012
Deleting the existing partition...then formatting...certainly eliminates malware from the hard drive, IMO.
Differences between a Quick format and a regular format during a clean installation of Windows XP - http://support.microsoft.com/kb/302686
XP Clean Install, Stevens - http://www.michaelstevenstech.com/cleanxpinstall.html Router Infections