I am looking for a usage metering algorithm which does not require either
special hardware or connection to internet, and is secure. This system might be
compared to printers and ink cartridges. The user buys a printer and an ink
cartridge, and when the ink runs out, buys another cartridge. We would like to
implement the same in software.

I fear what you try to do is theoretically impossible. Users can always control
the software (i.e. single-step and modify it). Or, much more likely, they can
run the software in a controlled environment (e.g. vmware) and after execution
simply reset the state of the virtual machine to what it was before the execution. 

You are missing a trusted environment. Are you sure you can not add additional
constraints to your usage scenario?

Even though what philip says is true, not 100% of the users are aware of this. 
The type of metering you put into your program would depend largely on the 
audience it is aimed at.

If it is aimed at "low-end" users (with not much experience) then they are not 
likely to change the environment that much, or if it runs using a network (as 
in more than one person can use it at a time) then the programs could 
synchronise with each other, meaning that <I>all<I> of the machines would have 
to be running in a simulated state.

Another thing to consider is how cost-effective the program is to fake. eg if 
the program costs $30 (or £20) every 6 months, but products like VMware can 
cost up to $300 (or £200), meaning that to copy it, they'd be spending 5 years 
worth of program use. (by which time its upgraded, or changed completly, etc)

This also depends on whether you are monitoring or actually charging per use. 
(although looking at your question suggests Pay-Per-Use)

The best option (although you'd rather not) is to use the internet.

M@

It's quite possible to protect a program's main executable file (in
Windows, it's the .EXE file you click on, or click on a link to, which
starts the program) by a) encrypting the file, and then b) running a
background service that monitors attempts to open the file and
decrypts its contents on-the-fly, after verifying that "metered" time
is still available for this file.

The actual metering information could be stored in an encrypted form
in the system registry or possibly in an encrypted file. This metering
information could be updated ("refreshed") via phone call or Internet
download at certain intervals.

One weakness in this design is that a sophisticated user could
determine the location of the metering information and backup/restore
it once a day, thus effectively making the available time last
forever. It may be possible to tie this information to the system
clock, in order to detect whether it has been backed up and restored,
but that's as far as I've taken this thought process so far.

HTH,
Philip

Actually, yes you can do this with hardware dongles.  Search google
for :

"Rainbow dongle"
"Aladin dongle"

Dongles have EEROM which allows you to store metering ussage
information seperately from the computer. Both of these technologies
can be "cracked" by a sophisticated user because all the software runs
on a untrusted system as a previous poster commented.  If security is
a high concern I have a system that allows you to remove small
portions of executable code from your EXE and translate the
instructions into 8-16 bit microprocessor code that runs on a secure
USB smartcard attached to a PC.  This is system is currently only
available in network form.

For more details search the USPTO (patent office) for Jonathan Clark
or contact me at jonathanclark.com

I'd have to agree with what I've seen so far. I once heard someone say
"If it can be written, it can be cracked" This was shortly after the
release of a new copy-protection method which was said to be
"uncrackable"

However as has also already been mentioned, depending on how advanced
or bothered the user is will determine the likelyhood of a success.