No need to reinvent video encoding. At least my local provider seems to fix this by having all the channels streamed as multicast continuously and then having the TV box request a small bit of video over normal TCP to do the channel switch immediately and only later syncing to the multicast. That allows you to change channels quickly at any time and starting to watch at whatever the latest I-frame was.

I notice this happening when IGMP forwarding is broken in my router and channels will only play for a second or two after being switched to and then stopping. Switch times are pretty good.