Both HOT (67) and the Technokats (45) used omniwheels in 1998. These are the earliest known omniwheels that I'm aware of.
/edit
Here are pictures of
45 and
67 in 1998. If you look really hard you can make out the omniwheels.
Here's a picture of
the omniwheel used by 45 in 1998.
Finally, here's a picture of both
omniwheeled robots in action in the National Semifinals at EPCOT. (Aside: Everyone who's interested in this kind of thing should take a look at the Technokats history project on their website. It has some great photos from the good ol' days.)