Randall studierte Marketing an der University of Mississippi und wurde 1988 als Doppelspieler in die Bestenauswahl All-American gewählt. Bereits bei seinem ersten Antritt bei einem Turnier der ATP Challenger Tour errang er 1991 an der Seite von Mark Keil den Doppeltitel in Birmingham. In der Folge spielte er erfolgreich mit wechselnden Partnern und stand in den Finalpartien von Winnetka, Whistler und Puebla. Ab Februar 1992 trat er wieder regelmäßig mit Mark Keil an. Nach einer gemeinsamen Viertelfinalteilnahme beim Turnier in Philadelphia errang Randall mit Keil in Scottsdale seinen ersten Turniersieg auf der ATP Tour. Kurz darauf standen sie im Viertelfinale des Masters-Turniers von Miami und im Mai des Jahres im Finale von Atlanta. 1993 konnten Randall und Keil ihren Titel in Scottsdale verteidigen. Ab Mitte 1993 trat Randall regelmäßig an der Seite von Brad Pearce auf. Gemeinsam standen sie unter anderem im Finale von Basel und im Halbfinale des ATP-Championship-Series-Turnier von Tokio. Zwischen Mitte 1994 und Mitte 1995 spielte Randall häufig mit Ellis Ferreira. Nach einigen gemeinsamen Auftritten mit Greg Van Emburgh bildete er bis Mitte 1996 regelmäßig das Doppel mit Kent Kinnear. Den dritten und letzten ATP-Doppeltitel errang er 1997 mit Greg Van Emburgh in Coral Springs. Seine höchste Notierung in der Tennisweltrangliste erreichte er 1993 mit Position 155 im Einzel sowie 1994 mit Position 39 im Doppel.
Sein bestes Einzelergebnis bei einem Grand-Slam-Turnier war das Erreichen der zweiten Runde von Wimbledon 1993, als er nach drei Qualifikationsrunden Andrei Tscherkassow klar in drei Sätzen aus dem Turnier warf. In der Doppelkonkurrenz erreichte er 1993 das Viertelfinale der US Open sowie in der Mixed-Konkurrenz mit Jill Hetherington das Viertelfinale der Australian Open.
Vereinigte Staaten
Sandon Stolle
Nelson Aerts
John-Laffnie de Jager
Basel
Byron Black
Toulouse
Jonas Björkman
Jakarta
Hongkong
Andrei Olchowski
Bologna
Jacco Eltingh
Julián Alonso