I believe since 1999. There was an advisory committee on the retention and remuneration for senior officials, which is now chaired by Carol Stephenson, that made a recommendation that there be at-risk pay as part of the compensation package for senior executives in the public service, including deputy ministers.
On November 7th, 2006. See this statement in context.