The problem is that not all database drivers supports the complete set of ado methods. For some the RecordCount only gives accurate information if MoveLast is called first. As you encounter, this method isn't working correctly. This means you have to improvise to to get compatible results. You could implement your own method and simply do:
do until rs.Eof
rs.MoveNext
loop
This link has some nice info on this:
http://flylib.com/books/en/3.405.1.32/1/[
^]
Good luck!