Well, since you're not talking about modding as such, but more about creating your own patch...
This used to be a legally protected right. You could patch your own software. (though you would have to do so without the aid of the original source code, which isn't a trivial task.)
However, more recent laws, such as the DMCA have cracked down on this.
Although even the DMCA contains provisions for reverse-engineering computer software for certain reasons...
Such as inter-operability.
Consider the case for instance where you have a business database, which contains large amounts of data that is critical to the running of your business.
However, the company that made it went bust, and you need to interface with this system somehow, (because replacing it altogether and porting across the data would be too complex maybe).
You are well within your rights in a situation like that to reverse engineer the program so you can get it to work with your newer systems.
Another example might be microsoft word. They've changed their policy in recent years, but for a long time the *.doc file format was completely undocumented.
This meant if you needed to read it, but didn't have access to microsoft software, your only option would be to reverse engineer the file format.
Which, again, is perfectly legal. (Except that certain file formats contain software patents. Eg. While it's legal to reverse engineer the MP3 format, the compression scheme is patented, so even if you succeeded, you'd need to licence the appropriate patent.)
So... Is patching a game you didn't make, illegal? That's circumstantial depending on what you're doing to it, and what your reasons for doing so are.
Also, in general, laws about such things have been getting more restrictive with time, so it's worth some degree of caution here.