As of 2006, HP introduced cartridge authentication technology which essentially disables the cartridge once it becomes empty i.e. by the time it first gives you an error message saying the ink is empty, the cartridge has essentially been disabled (electronically).
My understanding of the way it works is that the serial # of the cartridge is stored in the memory of the printer, thus if the cartridge is re-inserted, the printer rejects it as unauthentic / invalid.
The trick is to refill your cartridge at the 40-50% percent mark so that it never gets to the point where the cartridge can be disabled.
I believe there was a lawsuit against HP for this change, although I am not sure what happened to it. Please note that this only applies to the "newer" HP models which use the squarish ink cartridges such as the HP 56/57/58/26/27 etc..
It does not apply to the old, tall cartridges similar to #23, #82 etc...
Boy! This brings back memories of working on the front lines =)
edit: Here is a work around for disabled cartridges:
1. Remove cartridge from your printer.
2. Place a piece of tape over the top left contact as shown in red on the picture to the right.
3. With the tape covering the contact place cartridge back into printer.
4. The printer will perform and alignment page.
5. Once an alignment page has been printed remove cartridge from printer.
6. Place a piece of tape over the second contact shown in red.
7. Place cartridge into printer with both pieces of tape. (One covering the first contact and one cover the second contact.)
8. Printer will print another alignment page.
9. Once the second alignment page has been printed remove cartridge from printer.
10. Remove tape pieces from cartridge contacts (Make sure there is no residual adhesive on cartridge contacts.)
11. Place cartridge into printer. Cartridge should now read full.