There are just too many ways in which malware can persist on a Windows machine without touching the registry. For example:
Windows Startup Folder
Although it is the most simple and obvious to be found, still I am describing it here just to show that this technique doesn't require touching the registry. In Windows family of operating systems every user has a particular statup folder in which any executable or shortcut file placed will be automatically executed by the operating system upon user login.
For Windows XP and Windows Server 2003, the starup folder path is:
C:\Documents and Settings\"User Name"\Start Menu\Programs\Startup
For Windows 7 and Windows 8, the path is:
C:\Users\<User Profile folder name>\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Startup
If the malware is placed in the above locations, it will be executed every time the user is logged in and this technique doesn't require any modification to the Windows registry.
The malware can also infect pre-existing binaries and embed itself with the auto-executable executable files. For example, replacing uTorrent.exe with a trojanized uTorrent.exe in which the malware is embedded with the main executable results in execution of the legitimate program as well as execution of the malicious malware file and no mofification is required to be made to the registry (assuming that uTorrent.exe is in the auto-executable files list).
Just placing the malware DLL file at a particular location can also result in the execution of the malicious DLL file. This attack is commonly known as the DLL Hijacking in which the malicious DLL file is placed in a location that is searched first by the OS before it gets to the legitimate DLL path. Again, no changes is required to the registry for executing the malicious DLL through DLL hijacking.
We haven't even touched the BIOS persistent malware even though those techniques have also been publicly demonstrated. In short, there are too many techniques and methods through which malware can be executed automatically at boot time. Once the attacker gets hold of the machine, it is usually futile to detect it at that point. The detection should then move to the network and outgoing traffic from the machine should be analyzed. Note however, that you cannot run netstat, wireshark or any other tool on the compromised machine as rootkits can hide itself from any tool running on the compromised machine. Therefore, keeping in view the concept of defense in depth, you should analyze and protect your assets from the identified threats at multiple locations and hope that not every location can be compromised at once by the attacker.