In order for the Last Verified By and Tax Status Verify Date fields to update, you will need to select Tax Status 1 and 2 fields as well.

Click Tax Status Verify from the Actions menu
Click Details
Select Tax Status 1 and 2 and any other fields you want updated in the record
Click OK
Select the organization from the list
Click Update Organization.

The fields should now display the most recent verification information.