As a data point, on a 3.4.3 test system I do not see that the "This record has been deleted from the database" verbiage is sticky - it clears from the undeleted record as expected.
As a data point, on a 3.4.3 test system I do not see that the "This record has been deleted from the database" verbiage is sticky - it clears from the undeleted record as expected.