How to do a full factory reset and clean the phone completely?
As the firmware resides in /system, flashing a firmware obviously overwrites that partition. /boot is usually involved here as well. Whether the two get "wiped" is a different question; but as otherwise things could get "mixed", which might cause unwanted side-effects, I'd say they are (I'm not 100% sure with this). So in these two partitions, nothing of the previously installed firmware should remain.

That's different for the other partitions of your device. So usually, /data is not touched by the flashing process, but of course it will be touched once the new system boots up (it e.g. needs to initialize the dalvik cache for the newly installed system apps, which is located in /data/dalvik-cache). For the /cache partition (holding the application cache) it's similar: It usually is not touched by the flashing process, but used normally afterwards. Hence it's a good idea to wipe these two (Cache and Dalvik Cache) when installing a different ROM. It might not always be required, but it doesn't hurt.

A factory-reset in principle is a combination of the two: it wipes the /cache and /data Partitions. So other than the manual wipe of the caches from a custom recovery, it also removes all user data (including the user-installed apps).

Note: Don't confuse a "wipe" with a "safe erase": with the right tools, data still might be recoverable following a wipe.

With this on your mind, your second question becomes obsolete: if you just want a clean system for yourself, this wish is already granted. If, on the other hand, you did these steps to sell your device, there's always the point of what could be restored. For a "safe erase", you might want to take a look at special tools like Nuke My Phone / Nuke My Tablet, which overwrite everything with "garbage data", and finalize this process with a factory-reset.