Moderator edit 2020/04/20:
The research and its practical applications from this thread have been compiled on the following pages:
* List of console verified movies
* Console verification guide
* Console verification tests
Please refer to them for up-to-date information. Original post below.
As a school project I manged to play the current TAS record for SMB on the actual NES. I was also able to play the warpless run and the walkathon runs. I've been meaning to get my project info online for a while, but here are some quick details.
I used the Arduino Duemilanove as the controller for the whole thing. To connect to the NES, I used circuits similar to the ones on the link DarkKobold posted. I hooked the pulse line from the NES to one of the interrupt pins on the Arduino, and had an interrupt occur every time a pulse happened. This was the only reliable method I found to know when the NES wanted buttons.
I wrote a lua script to remove any frames that are marked as lag by FCEUX. Then by running my script when a movie is loaded, it will output only frames the NES would actually be interested in. I then stored this information to an SD card.
Doing this with SMB proved to be very reliable. Even if the NES starts in a semi-random state, the worst I had to do every time was restart the console once or twice and it worked fine. And if it started fine, it worked until the game was beaten. I've seen it run about 20-30 times consistently.
I tried a few other games including Marble Madness, and SMB3. Marble Madness seemed to desync quickly.
SMB3 was a lot more interesting. Looking at it on an oscilloscope showed that for every frame, the controllers are pulsed twice. However, looking at the disassembler, I saw that even though the controllers are pulsed twice each frame, only one is read per pulse. If I remember correctly, the second controller is read first, then the first controller. Anyway, when I found the double pulsing, I just changed my code slightly to hold each button press for 2 pulses instead of one.
It took quite a few console resets to get it to even get to the level select screen correctly. If it made it there, sometimes it would desync before even jumping over the pipe, causing him to die on the flower. Once or twice he did make it pretty far into the level, even jumping down through the block, but he got stuck.
I'll try to get the full details of my project up soon (source code, circuit schematics, etc).