I will need to write this quickly, please bear with me, but here goes:
Component GUIDs must stay the same between packages for files to update correctly, especially when you deploy via a patch. The key symptom of mismatching component GUIDs is exactly missing files after the deployment is complete (and patches that never work).
Set up a proper major upgrade as explained by PhilDW, and keep the component GUIDs consistent between releases and follow the component creation rules, and your upgrade should work correctly (and your patches too).
Note that you can leave the component GUIDs out of the WiX source file and allow them to be auto-generated rather than hard coded, and you will still get consistent GUIDs. Auto-generation of GUIDs will calculate a stable GUID (please read the linked question, the accepted answer along with all its comments) that remains stable between releases unless you rename or move the file in question - this requires a new component GUID, and here is why (this also explains why auto-generating stable GUIDs is possible). Auto-GUID generation will detect when a new GUID is required.
I am not up to speed on harvesting via heat.exe, but I think it allows the component GUIDs to be auto-generated rather than hard coded. Just change your script or automation process to set component GUIDs to auto-generate (this uses a * instead of a GUID in the component tag). Please read this entire answer with all answers and comments as well: Syntax for guids in WIX?
Important! A patch is just a delivery method for an MSI upgrade that is already working as a full package. Don't waste any time generating patches until you have verified that the full, updated MSI package upgrades the previous version correctly. You will just waste time if you do - the patch will never work if the full update doesn't work. It can't.
Is the first version of your product live? If it is not I would suggest starting over from scratch and use auto-generated GUIDs. If your previous version is live and you have hard coded component GUIDs you either need to match the existing component GUIDs in your first version with the component GUIDs in the updated version, OR you must put RemoveExistingProducts early in the InstallExecuteSequence as suggested by zett42 to allow the old version to fully uninstall before the new version is installed. This will prevent the previous error in component referencing to affect the major upgrade and no files should be missing after the upgrade. Patching will not be possible in this approach at all since component referencing isn't correct. This makes both minor and major upgrade patching fail - both require 100% component referencing to work properly.
This has already become long. If this all sounds Greek to you, please read up on the linked stackoverflow answers and get your head around MSI component creation best practice and component referencing in general. See MSDN as well for this. I will check back and see how you get on, and perhaps clean up this answer a little bit once I know what isn't clear and where you are at.