This issue is significantly impacting the company I work for. They have an order form that does significant data validation.
Each sheet in the workbook is protected so that data entry is only allowed in unlocked cells. The data entered is than validated by macros in worksheet_change events. If the data is found to be invalid the color of the cell is changed and often a comment is added. Unfortunately adding a comment from a macro requires unprotecting the worksheet.
In Office 2010 we just unprotected all the sheets in the workbook since the time taken to unprotect was unnoticeable to the user.
For our potential upgrade to Office 2013 we scaled the protection back to the minimal required (just the sheet being currently modified) and the delay doing the single sheet unprotect to add the comment is significant due to it slowing the data entry process for the user.
Frankly they are not worried about the complexity of the encryption. The only reason for the protection is to protect the structure / formulas / contents of the hidden cells / validation logic to allow the order form to be auto uploaded, without the user accidently corrupting the document.