I think that the first recorded use of bullet time was in Kill and kill again in 1981.

Here is a link to the wiki entry: http://en.wikipedia.org/wiki/Kill_and_Kill_Again

Here is a summary of what wiki says about it:

>Kill and Kill Again is a 1981 South African/American action film notable for being the first live-action film to use the visual effects known as bullet-time. It is a sequel to Kill or Be Killed (1980). Filmed in Sun City, Bophuthatswana, the film has a more tongue in cheek comedy approach than its predecessor.

> The bullet-time scene occurs at the end, when Marduk has died and his
> chief guard is about to kill Dr. Kane while Steve is climbing up the
> outside of the building they're in. The guard fires his gun (at
> 1:36:10) and the bullet comes out very slowly and moves across the
> screen in a recognizable (but low-budget) early version of the famous
> scene in the Matrix. After ten seconds of the bullet flying across the
> room, Steve Chase has gotten up the building, gets inside the room,
> and deflects the bullet with a metal ashtray.
> 
> This very low-budget "Bullet-Time-Slice" sequence was achieved very
> simply, in-camera, with no post-production effects. The first shot of
> the bullet exiting the barrel of the gun was shot in close-up, with
> the barrel removed from the frame of the gun locked-off pointing
> downwards but with the camera also turned on its side, framing the
> barrel horizontally, but pointing down toward the floor. (When viewed
> 'upright,' this would then appear to be pointing at the subject in a
> correct manner.) A bullet, smaller in diameter than the inside of the
> barrel, was then dropped down through the barrel along with a puff of
> smoke from a cigarette. The bullet-and-smoke shot was filmed at 120fps
> to create the desired effect.