Actually, GIF was patented for a very, very long time:

http://en.wikipedia.org/wiki/Graphics_Interchange_Format#Uni...

LZW patents only expired in 2003. Before that, GIF was not only patented, but the patents were actively (and often obnoxiously) enforced by Unisys. The situation was similar to that of MP3 with Frauenhofer in the late 1990s.