>How can I quickly count the number of undeleted records in a table?

"Undeleted" as in "not deleted", or as in "deleted and then recalled"? The others have answered the first case; for the latter:

set deleted off
recall for (your condition here)
?_tally
set deleted on

You have to save the value of _tally immediately after Recall, otherwise it will change as soon as you issue any other command which may operate on more than one record (count, delete, replace, update, select, list, copy...).