Bien, no sabría que estaba en decimal. Estoy codeando a ver si lo consigo de una vez.

Edito: ¡Por finnnn!, ya puedo irme a dormir contento. He aquí la JODIDA solución:

BYTE *bMacAddr = (BYTE*)&MacAddr;
			string res;
			stringstream ss;
			for (int i = 0; i < PhyAddrLen; i++)
			{
				ss << hex << (int)bMacAddr[i];
				res += ss.str();
				ss.str("");
			}
			*mac = _strdup(res.c_str());	

Gracias ivancea96 por la ayuda. It works like a charm.

Saludos.