Regex.Replace () имеет перегрузку, которая принимает делегата MatchEvaluator. Этот делегат принимает объект Match и возвращает строку замены. Нечто подобное должно работать на то, что вы хотите.
regex.Replace(text, delegate(Match match)
{
return string.Format(@"src=""/relative/image.ashx?imageUrl={0}""", HttpUtility.UrlEncode(match.Groups[1].Value));
});