This turns out to be non-trivial.
@godbyk, I'd appreciate your help. I have

\makeatletter
\newcommand{\customlabel}[2]{%
\protected@write \@auxout {}{\string \newlabel {#1}{{#2}{\thepage}{#2}{#1}{}}} %
\hypertarget{#1}{}%
}
\makeatother
\newcommand{\clauselabel}[1]{\customlabel{#1}{Clause \thechapter}}
\newcommand{\annexlabel}[1]{\customlabel{#1}{Annex \thechapter}}
\newcommand{\tablelabel}[1]{\customlabel{#1}{Table \thetable}}

in macros.tex, and then

 \caption{\tablelabel{#2}#1}%

in tables.tex (where we used to have \label).

It seems the \tablelabel macro only works outside of \caption. Inside, the error message is

! Argument of \Hy@tempa has an extra }.
<inserted text> 
                \par 
l.400 ...alternative.tokens}{Alternative}{Primary}

But outside, I get additional blank vertical space after the table caption (and before the actual table), which is undesirable. Any ideas?

Ah, I found a solution: Adjust \tref and do not attempt to modify the stuff written into the .aux file.

\renewcommand{\tref}[1]{\hyperref[tab:#1]{\tablerefname \nolinebreak[3] \ref*{tab:#1}}}

@jensmaurer That's the solution I used for another project. Mine was slightly fancier in that it checks to see if the tab: prefix is provided and only inserts if it isn't. Here's the example code from it, for future reference:

% Macro to simplify linking to chapters
\newcommand{\chaplink}[1]{%
  % not using \autoref here because I don't want to fix the case of \chapterautorefname for individual languages --godbyk
  \IfBeforeSubStringEmpty{ch:}{#1}{\hyperref[#1]{\@chapapp~}\ref{#1}\hyperref[#1]{: }\nameref{#1}}{\hyperref[ch:#1]{\@chapapp~}\ref{ch:#1}\hyperref[ch:#1]{: }\nameref{ch:#1}}%
}

% Macro to simplify linking to sections
\newcommand{\seclink}[1]{%
  %\IfBeforeSubStringEmpty{sec:}{#1}{\autoref{#1}\hyperref[#1]{: }\nameref{#1}}{\autoref{sec:#1}\hyperref[sec:#1]{: }\nameref{sec:#1}}%
  \IfBeforeSubStringEmpty{sec:}{#1}{\nameref{#1}}{\nameref{sec:#1}}%
}

The result was that you could write either \chaplink{ch:blah} or \chaplink{blah} and they would both give the same result. If your authors are more consistent, you can skip that error correction, though.