The factory reset on any phone/computer shouldn't be trusted, as it can be modified by the system and thus becomes a heaven for malware that wishes to persist. This also applies to the Windows 8 "refresh my PC" feature, the "recovery partition" nonsense OEMs put up to avoid supplying $0,01 recovery DVDs (which are write-once media and can't be compromised) and any similar feature.
To properly "nuke and reinstall" a phone, you should use a known good machine to download a clean ROM image (either an official one or a third-party one you trust), reboot the device in bootloader/DFU mode (for iPhones) and then install the image (in the Android and Windows phone worlds, a nice bonus is that you have the chance to install a non carrier-branded ROM and say goodbye to their bloatware and lack of updates).
Theoretically the bootloader itself could be compromised and evil, and at this point there isn't much to do besides physically unsoldering the memory chips from the phone and writing a new firmware & bootloader to them from a clean machine. The only reason these attacks aren't more widespread is the same as for malicious BIOSes for PCs - the fact that this kind of malware isn't portable and targets only a single make/model of machine and the difficulty needed to develop such malware (a lot more complicated than your average malware running in userland).