A couple of random thoughts.
Deleted records in a table are not actually deleted but all records on a page are overwritten with the first record.
Perhaps the count error doesn't manifest until the number of records exceeds one page?
What indexes are on the table? A DCount will use an index if it exists. Maybe RecordCount property would too. Would be interesting to see if that makes a difference to the count.
BTW The first parameter of Domain Functions is not a field name (as many developers assume). It is an expression. A DLookup will return the results of the expression which will include values from the fields included in the expression if present.
Anything that evaluates to an alphanumeric string will be used as a fieldname. Those that evaluate to numbers or Booleans are quietly accepted in a DCount to mean all. So if you want to use a digit instead of "*" you might as well omit the double quotes too.
I haven't dug into it enough to isolate a specific set of circumstances. But I don't understand your statement here, "...all records on a page are overwritten with the first record."
I thought the space was just marked as available. Why would a 'first record' be written everywhere? That seems pointless and error-prone. And if it was, you would have multiple copies of a record, when quite possibly the table has restrictions that do not even allow duplicates, like an autonumber primary key. A command to delete all should do just that, and nothing more.
I haven't investigated the issue of indexes. Seems an interesting point, though. Also dropping and recreating indexes after the delete might make a difference. I'll look at it and post back here if I come up with anything.
And thanks for the tip about DCount. I've just gotten into the habit of using "1", but for the purposes of simply counting, when I am forced to put in the first parameter even though I have no interest in the contents of that parameter, I think rather than "1" a simple zero would be clearer, and I am going to switch to that.