I went back to Michael’s post, did some more poking and realized that I did need to do a double conversion, and eventually worked out this little nugget:
Convert.ToString(Convert.ToChar(Int32.Parse(EncodedString.Substring(intParseIndex, 2), System.Globalization.NumberStyles.HexNumber)));
From there I simply made a loop to go through all the characters 2 by 2 and get them “hexified” and then translated to a string.
To Nick, and anybody else interested, I went ahead and posted my little application over in CodePlex. Feel free to use/modify as you need.