When you delete a record in the Governance Portal, the record is no longer accessible through the user interface, but is actually not "physically" deleted from the system. When you click Submit at the Remove all Deleted Records link, you will be "physically" removing these items from the database and shrinking the database size down for more efficient operation.