Locking A Worksheet But Allowing Hyperlinks?

I have a problem where a client is asking to have an Excel Spreadsheet completely secured. In itself this is a relatively painless exercise, but the problem lies in the fact that the workbooks have a lot of cross-sheet navigation by way of internal Hyperlinks.

My first thought was to unlock the cells that contain the the Hyperlinks and then allow selecting unlocked cells in the sheet protection properties, but this has an adverse affect in that it means clicking anywhere on the page will execute the hyperlink as if you had clicked on it directly. This isn't going to be sufficient in this case.

The Hyperlinks are simply added to the cell itself, but there are a lot of them and this template may be processed and updated up to 1000 times a month, so I need something that can handle being automated. My only other thought is to hand the document over to Acrobat and PDF it to allow security, but automating PDF creation is testy at the best of times.