Mil gracias Myakire, estaba buenisimo, solo habia que asignarle a Estado = "" para cuando no encontrara el ID, pero era solo eso.
Voy a dejar el codigo por si a alguien mas le interesa
Do while not rs5.EOF
Response.Write ("<tr>")
For i = 1 To 7
If Not rs5.EOF Then
Response.Write("<td width=""14%"" height=""22"" align=""left"" valign=""top"">")
Response.Write("<label class=""texto11n"">")
if InStr(Request.Form("Categorias"),rs5.Fields("id_ca t"))>0 Then
Estado = " checked "
else
Estado = ""
End If
Response.Write("<input type=""checkbox"" name=""categorias"" value=""'"&rs5.Fields("id_cat")&"'"" " & Estado & ">")
Response.Write(""&rs5.Fields("nombre")&"")
Response.Write("</label></td>")
rs5.MoveNext
End If
Response.Write("</td>")
Next
Response.Write("</tr>")
Loop