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. Im Februar 1994 erreichte er damit Platz 39 in der Doppel-Rangliste. 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 Randall 1997 mit Greg Van Emburgh in Coral Springs. Im Einzel kam er zu keiner Finalteilnahme auf der ATP Tour und nur zu zwölf Turnierteilnahmen dort. Seine höchste Notierung erreichte er 1993 mit Position 155.
Bei einem Grand-Slam-Turnier spielte er im Einzel zweimal, sein bestes Resultat war das Erreichen der zweiten Runde von Wimbledon 1993, als er nach drei Qualifikationsrunden Andrei Tscherkassow 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.
Nachdem er bereits 1994 den Turnierbetrieb im Einzel eingestellt hatte, trat er im Doppel noch bis 1998 regelmäßig bei Turnieren an. Danach folgten bis 2008 noch gelegentliche Teilnahmen.
Vereinigte Staaten
Sandon Stolle
Nelson Aerts
Brest
John-Laffnie de Jager
Basel
Byron Black
Jonas Björkman
Jakarta
Hongkong
Andrei Olchowski
Bologna
Jacco Eltingh
Julián Alonso