I've found (maybe it's surprise only for me?) that when you issue the commands - you typically get different results. The first returns cursor containing a set of records (depending on your SET DELETED it's all records or only not deleted ones).
The second command returns (I would say 'always' - but can't) number of all records ignoring SET DELETED setting.

There is one exception: When you have index tag on DELETED(). In the case SELECT COUNT(*) returns the number of not deleted records.

I'm wondering if it's caused by a bug in rushmore optimization or I don't understand something?

CREATE TABLE newtable FREE (fld1 C(10))
APPEND BLANK
APPEND BLANK
DELETE
*Without index on deleted results differ
SET DELETED ON
SELECT * FROM newtable
?RECCOUNT('newtable')
SELECT COUNT(*) FROM newtable
?query.cnt
*Exception?
SELECT newtable
INDEX ON DELETED() TAG dltd
SELECT * FROM newtable
?RECCOUNT('newtable')
SELECT COUNT(*) FROM newtable
?query.cnt