I'm not an Android developer or expert in any way, but I do know that the storage of the phone is divided up into several different areas/partitions. A Factory Reset will only clear some of those areas. The Dalvik Cache is one such area (I think), which is left untouched. Also, if you have the phone set up to automatically restore software and settings it may re-introduce an earlier problem even following a factory reset.
The best way to make sure you have a completely blank sheet to start from is to wipe some of those additional areas. Unfortunately such options are not made available with the stock ROM. For my Note I flashed "Philz kernel", which gave me those extra options. Then I used PC Odin to flash a clean stock ROM onto my clean Note.
Clearly that is more than the average phone user should be expected to do, but it does seem to be the recommended approach if you are running into problems, or to prevent them in the first place.
Philz kernel for the Note, with additional recovery features, can be found here....
All mods at your own risk.