Viruses work in various ways...
AFAIK, most viruses today don't actually do exe-infection, they simply store their executables somewhere and use means of adding them to the windows startup. This can be done in more or less sophisticated ways - some viruses employ rootkits that can make detection and removal pretty darn different. And things like hooking winsock TDI providers makes f0dder go argh.
For exe infection, there's lots of ways to go about it as well. On NTFS, alternate data streams can be used to hide the payload. The usual method is appending virus code to the executable code section, though. Then either the start of the executable is overwritten to jump to virus code then back, or the executable entrypoint is redirected to the virus code, or... in the case of evil polymorphic engines... sometimes the virus body is actually merged/interleaved with the normal executable code, making disinfection more or less impossible.
In the case of "restoring original instruction", that is only done in-memory, so virus payload will run every time an executable is run.
Also, windows doesn't have a "terminate and stay resident" concept like DOS had, so if a virus wants to keep running (to infect executables in the background, or join a botnet, whatever) it has to keep code running in memory somehow. Users would be suspicious if they close an application and it doesn't disappear from the windows task manager list, so a virus can't just keep the original executable running. Various schemes are used... some viruses try to inject themselves into already running programs (usually explorer.exe, since it's always running on any normal windows install), some run a rootkit-hidden executable, some have virus code entirely in driver components, et cetera.
IMHO if you have an infected system, the only way out is a total windows reinstall. Trying to "clean" systems, when dealing with anything but simple malware, has too great risks of missing an infected file, or causing executable corruption in the removal phase.