No comentas la BD que usas, ya que con ADO puedes conectar a varias de ellas. De todas formas, se me ocuurren 2. Algunas Base de Datos poseen una tabla (sysObjects, por ejemplo para SQLServer) donde están todos los objetos de la BAse de Datos, basta con que consultes si hay algun elemento de tipo tabla con ese nombre. Otra más "ruda", pero más simple, es lanzar una SQL como ésta:
Y capturar el posible error (por si no existe); Si no da error es que ya existe.
MEJORA: Haz un TOP 1 (si lo permite) y pregunta por un único campo en lugar de por todos (*).