Well, there's also the fact that the system only has 256MB of user-available data. :/
360 did patches in less than half that for the first three years. You can't test it now because the NXE requires a storage device and all new Xboxes come with at least 4GB of storage space, but before that it downloaded both the firmware updates and game patches into a tiny amount of non user-available embedded storage.
Patches were limited to 5MB or less until around 2010 (which was never an issue except for games like Burnout Paradise that added significant content for free), and the system automatically only cached the most recent 5 in order to limit the total size.
I really think that there's something about either the system or NWFC that makes patching difficult to implement.
Patching as a general process is not difficult.
A patch is essential a series of filenames, each with a series of memory offsets, each with a new value. A general purpose patch application layer is simply an OS level interrupt running at the file read level that says:
When I read a byte or more of a file into memory, read it into memory, then read the patch table looking for entries that correspond to the same byte. If there are some, overwrite what I just read into memory. Provided they are not able to allocate any memory to hold the patch, they can do it ad hoc on file reads like I just described. Provided they were willing to actually make their system API more efficient, they could load the entire thing into memory in advance of playing the game and read it from memory. This would be done at the iOS level.
Microsoft's entire OS ran in 16 megabytes of RAM for the longest time. That includes voicechat, friends, messages, achievements, presence data, always-on notifications, the guide itself, custom soundtracks, etc. Sony's still uses significantly more than that but I understand they reduced their footprint by >75%. I have no idea how much RAM system libraries / IOS take. I can tell you that hackers have added significant functionality at the IOS level (universal USB read/write support, for example), which tells us three things:
1) It is relatively simple to add new functionality to IOS
2) However much RAM Nintendo allocates for IOS (which is entirely loaded into RAM on game boot), they don't use 100% of it, because functions have been added without causing memory-related crash issues.
3) Nintendo's read/write system calls are sufficiently asynchronous that slower or faster than expected read/writes do not gum up the works and it would be possible to add an additional flash memory file-read into IO routines without tanking system performance.
The NWFC thing might be prohibitive simply because it's impossible to do anything on the Wii online without having to wait forever for it to establish a connection, but again everyone knew this well before 2006 so if Nintendo didn't, or didn't see the value, that's their failure, not a "hindsight is 20/20" moment.