Estimado Garet, primero que nada SI puedes regresar al primer registro del recordset siempre y cuando utilices el cursor adecuado, por ejemplo adOpenStatic o adOpenDynamic, no así con el adOpenForwardOnly que debe ser tu caso.
Si abres el recordset utilizando uno de estos cursores (Static o Dynamic) puedes utilizar una simple propiedad del objeto recordset que es RecordCount para obtener la cantidad de registros, o sea que podrías poner:
Dim cantidadregistros
cantidadregistros = miRecordset.RecordCount
Pero si estás utilizando un cursor de tipo adOpenForwardOnly tienes otra opción que es utilizar GetRows para obtener todos los registros de una vez, o sea que quedaría algo como esto.
Dim cantidadregistros
Dim arrRegistros
arrRegistros = miRecordset.GetRows
cantidadregistros = UBound(arrRegistros, 2) + 1
Tienes que sumarle uno, puesto que GetRows devuelve un array bidimensional con toda la información de los campos y registros de la consulta y como todo array su primer indice comienza por 0 en lugar de por 1.
El tema de GetRows

es un poco más profundo que esto y tiene unas utilidades excelentes para acelerar la devolución de la información desde la base de datos, pero para lo que la necesitás con esto es suficiente.
Espero que te sirva.
Saludos