Googleで検索かけるとこんなのが出てきましたが・・・。
[VB6] SP5 : レコードセットにレコードを追加すると "ブックマークが無効です" のエラー
http://www.microsoft.com/japan/support/kb/articles/JP281/8/87.htm

いえ、追加する段階ではなく、使用するレコードを読み込む段階でエラーが発生するん
です。
しかも、おなじ条件で処理をしても、発生するときとしないときがあるんです。

上記のドキュメントの結論は、クライアント側にインストールされているMDACのバージョンによって起こるようですが、その辺りは確認されましたか？クライアントマシンのOSとか環境もきちんとかかれないとなんともいいがたいのですが。逆に聞きたいのですが、まったく発生しないクライアントPCは存在しますか？存在するならば、それらのMDACのバージョンとかはどうなってますか？異常が発生するレコードはは特定のレコードですか？それともレコードにまったく関係なしに発生するのでしょうか。あと、VB6のServicePackは何があたってますか？

補足ですが、IEのバージョンも確認されたほうがいいと思います。ActiveX関連ですので。

ＶＢのサービスパックはＳＰ５を当てています。
ＭＤＡＣについては、ＳＰ５に入っていたものをインストールしているので、２．５です。
ＩＥのバージョンについては、最新のものでも４．０１で、ほとんどの機体は
Ｗｉｎ９５の標準のＩＥです。
全ての機体で同様のエラーが発生します。
発生するのはファイルをオープンしようとする段階なのですが、レコードに関係なく発
生します。そして、おなじレコードでも発生するときとしないときがあります。

なるほど。ということは、データベースそのものではなくネットワーク環境に何か不具合がありそうですね。サーバとクライアント環境間のプロトコルはTCP/IPでつながってると思いますが、それ以外のプロトコルがありませんか？NetWareとか・・・。
ネットワークそのものに負荷がかかっているとか、どこかのハブが壊れかかっててデータ転送中にデータが化けてる感じがしなくもないのですが。
あと昼間の方が発生頻度は高いのでしょうか？夜の方が発生しにくいとかあれば、トラフィックがらみだと思うのです。

ネットワーク側ですか・・・わかりました。環境を洗い直してみます。
どうもありがとうございました。