IF Nintendo says anything official regarding runs such as these, it will almost certainly be that they are illegal.
The AVI is made up of two parts...
1) The FMV (a set of button presses), and
2) The Rom (a set of game data, including sound and graphics).
The FMV is clearly owned by the creator; any FMV is theoretically compatible with any other game -- it just so happens that it's only a recording of keypresses. You could play a Zelda 2 FMV on a Rockman 2 rom, or a Batman FMV with a Super Mario Bros rom. Therefore, the FMV is clearly an independent creation by the player, that theoretically might even be able to be used to play another game independent of the one that it was made for.
The legal difficulty is related to the ROM itself.
First of all, the sound and graphics of the ROM are owned by Nintendo (as they licensed basically all of the games) or by their parent company (in the case of expired licenses, and unlicensed games, such as those from Tengen).
As the AVIs are entirely made up of sounds and graphics from a single source (i.e. the Legend of Zelda speed-run is entirely made up from the Legend of Zelda video game), it's hard to support its claim as a qualified "derivative work".
When Boco suggested "derivative work", she's probably thinking of the largely unregulated Japanese doujinshi (roughly analogous to a "fan comic") markets. For those not "in the know", Japan has a thriving trade of underground comics, some of which are based off of characters produced by major studios. For instance, it's not hard to find doujinshi of characters from Sailor Moon, Dragon Ball Z, the various Final Fantasy games, and so forth. However, as evidenced by Nintendo and several court cases in Japan, companies -do- retain their character rights, and as such the wholescale lifting of characters and remolding them into ones own story is probably illegal.
Derivative works are more likely to be protected when there's a significant amount of personal creation involved. However, any time any story, thematic elements, or characters are used, it's a potential violation of copyright.
An example of a derivative work might be, for instance, some of the hacked roms floating around. Games that have been retooled (new graphics, new sounds, new maps, etc... leaving only the basic engine) are more likely to withstand a legal assult regarding their derivative nature.
This is ignoring, of course, the fact that the ROM is clearly illegal -- the only legal ROMs are "Public Domain" ROMs, and ROMs made by someone for the sole purpose of backing up the data for archival (and thus restoration) purposes. ROMs that are downloaded or made for any purpose other than back-up storage and restoration are illegal.
The AVIs are just video reproductions of a ROM in synch with a FMV. Because the ROM is illegal, and the video reproduction is not a new creation (or a derivative work), thus the AVI is probably illegal, too. Furthermore, the AVIs record a direct "win" of the game, thus accomplishing exactly what one would normally buy a video game for (or at least, such could probably be argued in a court of law when supported by sociological/economic evidence about video game purchasing and playing trends)...
At least, that's my two not-a-lawyer cents on the situation, at least for those of us based in America. Your laws may vary by country.