Apple, Google and Microsoft already have licenses for H.264. All Mozilla would need to do is have Firefox call the OS' built in video playback (Apple's QuickTime API, Microsoft's Windows Media Player API, etc).
Yes, that spectre does exist, but I would expect the same response that caused PNG to be created for lossless image compression would happen for video.