まずメッセージボックスでやるのは面倒かと思います。
メッセージボックスは出来上がっているので、それに手を加えるのは大変です。
(過去ログでSetWindowsHookExをキーワードに検索してみてください)

メッセージボックスではなく、自作のダイアログでやるのではダメなんでしょうか？

自作のダイアログであれば、ここが参考になると思います。（MFC）
http://www.geocities.co.jp/SiliconValley-PaloAlto/1053/mfc/makelink.html

URLを表示すれば、勝手にハイパーリンクとして動いてくれるような
便利な物は多分無いと思うのでさやびさんが書かれているように
自分でダイアログを作成してゴリゴリプログラミングして実現するしか
無いと思います。
原理的には難しい話ではないと思うので後は地道に実装するだけだと思いますよ。

>まずメッセージボックスでやるのは面倒かと思います。
やってみました。
SetWindowsHookExでメッセージボックスをフックしてサブクラス化しています。

※文字数オーバーになってしまったので２回に分けます。

// リンクメッセージボックス
// 参考： http://hp.vector.co.jp/authors/VA016117/dlglink.html
#include <windows.h>

#define COUNTOF(ary) (sizeof(ary) / sizeof(ary[0]))

HHOOK hMsgBoxHook;
HWND hMsgWnd;
int nStaticID;
WNDPROC pOrgProc;
TCHAR szCaption[256];
HBRUSH hBrush;
HFONT hFont;
HCURSOR hCursor;

LRESULT CALLBACK LinkMsgBoxProc(HWND hDlg, UINT msg,
WPARAM wParam, LPARAM lParam)
{
HDC hDC;

switch (msg)
{
case WM_CTLCOLORSTATIC:
hDC = (HDC)wParam;
::SetTextColor(hDC, RGB(0, 0, 255));
::SetBkMode(hDC, TRANSPARENT);
::SelectObject(hDC, hFont);
return (LRESULT)hBrush;
case WM_SETCURSOR:
if ((HWND)wParam == ::GetDlgItem(hDlg, nStaticID))
{
::SetCursor(hCursor);
::SetWindowLong(hDlg, DWL_MSGRESULT, MAKELONG(TRUE, 0));
return TRUE;
}
break;
case WM_COMMAND:
if ( LOWORD(wParam) == nStaticID)
{
TCHAR szURI[256];
::GetDlgItemText(hDlg, nStaticID, szURI, COUNTOF(szURI));
::ShellExecute(hDlg, NULL, szURI, NULL, NULL, SW_SHOW);
return TRUE;
}
break;
}
return ::CallWindowProc(pOrgProc, hDlg, msg, wParam, lParam);
}

後半部分

HCURSOR GetFingerCursor()
{
HCURSOR hFinger = NULL;
TCHAR szWindowsDir[MAX_PATH];

::GetWindowsDirectory(szWindowsDir, COUNTOF(szWindowsDir));
lstrcat(szWindowsDir, TEXT(\\winhlp32.exe));
HINSTANCE hInstHelp = ::LoadLibrary(szWindowsDir);
if (hInstHelp)
{
hFinger = CopyCursor(::LoadCursor(hInstHelp, MAKEINTRESOURCE(106)));
::FreeLibrary(hInstHelp);
}
else
{
hFinger = LoadCursor(NULL, IDC_ARROW);
}
return hFinger;
}

HFONT GetUnderlineFont(HWND hWnd)
{
LOGFONT lf;
HFONT hOrgFont = (HFONT)::SendMessage(hWnd, WM_GETFONT, 0, 0L);
::GetObject(hOrgFont, sizeof(lf), &lf);
lf.lfUnderline = TRUE;
return ::CreateFontIndirect(&lf);
}

LRESULT CALLBACK CBTProc(int nCode, WPARAM wParam, LPARAM lParam)
{
switch ( nCode )
{
case HCBT_ACTIVATE:
if (!hMsgWnd)
{
// MessageBoxかどうか
TCHAR szTitle[256];
if (::GetWindowText((HWND)wParam, szTitle, COUNTOF(szTitle))
&& !lstrcmp(szTitle, szCaption))
{
// MessageBoxウィンドウハンドル取得
hMsgWnd = (HWND)wParam;

// MessageBoxのStaticコントロールの
// ウィンドウハンドル/コントロールIDの取得
/*
nStaticID = 0xFFFF;
HWND hStatic = ::GetDlgItem(hMsgWnd, nStaticID);
*/
HWND hStatic =
::FindWindowEx(hMsgWnd, NULL, TEXT(Static), NULL);
nStaticID = ::GetDlgCtrlID(hStatic);

// SS_NOTIFYスタイルの追加
LONG style = ::GetWindowLong(hStatic, GWL_STYLE);
::SetWindowLong(hStatic, GWL_STYLE, style | SS_NOTIFY);

// 必要GDIオブジェクトの作成/取得
hBrush = ::GetSysColorBrush(COLOR_3DFACE);
hFont = ::GetUnderlineFont(hStatic);
hCursor = GetFingerCursor();

// サブクラス化
pOrgProc = (WNDPROC)::GetWindowLong(hMsgWnd, GWL_WNDPROC);
::SetWindowLong(hMsgWnd, GWL_WNDPROC, (LONG)LinkMsgBoxProc);
}
}
break;
case HCBT_DESTROYWND:
// MessageBoxかどうか
if (hMsgWnd == (HWND)wParam)
{
// サブクラス化解除
::SetWindowLong(hMsgWnd, GWL_WNDPROC, (LONG)pOrgProc);
hMsgWnd = NULL;

// 各GDIオブジェクトの破棄
::DeleteObject(hFont);
::DestroyCursor(hCursor);
}
break;
}
return ::CallNextHookEx(hMsgBoxHook, nCode, wParam, lParam);
}

int LinkMessageBox(HWND hWnd, LPCTSTR lpText, LPCTSTR lpCaption, UINT uType)
{
int result;
hMsgWnd = NULL;
lstrcpy(szCaption, lpCaption);
hMsgBoxHook =
::SetWindowsHookEx(WH_CBT, CBTProc, NULL, ::GetCurrentThreadId());
result = ::MessageBox(hWnd, lpText, lpCaption, uType);
::UnhookWindowsHookEx(hMsgBoxHook);
return result;
}

ソースを提示されていれば、ほとんど丸写しで出来ちゃいそうですが、
知識がない人が一からこれを考えるのはたぶんかなり面倒でしょうねぇ。
ただ、どうやればメッセージボックスを乗っ取って弄れるかと言う
サンプルとしては良い物だと思います。
私も参考にさせていただきます。