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.