It's more restrictive then that. Not only does it need to be H.264 it has to be in an MP4 container with the MOOV atom at the start of the file. That last part is important because when you encode an MP4 file the MOOV atom is typically put at the end because it contains information that you don't know until after the file has been completely encoded. So to move the MOOV atom to the start you basically have to rearrange the file after it's been recoded, which is an extra step most people don't take. The reason TiVo needs it at the start is because the MOOV atom also contains information that is necessary to decode and play the file. And with network streaming you don't have random access to the file like you would on a PC so you can't simply seek to the end and read it. They'd have to wait for the complete file to transfer which messes up the TiVo's ability to start watching the podcast immediately. Basically MP4 was not really designed with streaming in mind so you have to take special steps to make it work that way.
Developer for VideoReDo