Быстрое решение, которое использует обычные (хотя и не стандартные) функции:
std::string input = MY_ENCODED_STRING;
unsigned long decoded_value = strtol(input.c_str(), NULL, 64);
char buffer[100] = {0};
std::string output = itoa(decoded_value, buffer, 16);
boost::lexical_cast
может предоставить более элегантное решение (хотя и не уверен в этом).