Que hago con este problema..

[maestro]

Bueno, si solo es ese el problema puedes solucionarlo añadiendo un campo llamado preferente (por ejemplo), y marcandolo como TRUE.
Imaginate que tienes 50 registros y solo marcas 10 como importantes, esos registros seran los que tendra en cuenta unicamente el generador aleatorio y no todos los elementos de la tabla, con lo cual existen muhcas mas posibilidades de que no se repitan.

Quedaria algo asi:

<%
set oConn=Server.CreateObject("ADODB.Connection")
set rs=Server.CreateObject("ADODB.Recordset")
oConn.Open "Provider=Microsoft.Jet.OLEDB.4.0; Data Source="&Server.MapPath("tubase.mdb")&";"
SQL="SELECT * FROM tutabla where preferente=true"
rs.OPEN sql, oconn, 3, 1
intTotalRecords = rs.RecordCount
Randomize()
intRandomNumber = Int((intTotalRecords * Rnd))
rs.Move intRandomNumber
' Ahora vamos a mostrar los valores de campo de ese registro aleatorio.
response.write(rs("campo1"))
response.write(rs("campo2"))
%>