The first US broadcasts in 720p appear to be in the late 1990's. CBS was broadcasting in 1080i in 1998. NBC followed in 1999. ABC was broadcasting in 720p in 2001. Fox, however, didn't switch to 720p until 2004. So saying that "720p and 1080p didn't exist" back then is not correct by a long shot. I don't know when Kings games first started getting broadcast in HD, but the format definitely existed and was in widespread use at the time.
Again, Google is your friend.
Again, Google is your friend.