Answer
The compression takes a long time if many records are deleted. Currently, the delete operation requires a full table scan for each record. This operation is optimized to perform a range scan for the delete, vastly improving the performance of the compress operation.
This problem is addressed in ArcGIS 8.1 Service Pack 1. See the Related Information section to download this pack.