VBAからUnicode版のWindows API を使う
この文字化け、実は最新版でも起きてしまう。
このためMsgBoxExが必要です。
と、当初肝心のAPIの部分がなかったので追記します。
自分が試したのとAddoinBoxは大体同じでしたが、Wih64は条件分岐編纂命令（Const Directive、条件付きコンパイル）は不要だと思います。
PtrSafeをつけていると基本的に32Bitにも対応できるため、つけなくていいです。
あと、通常のMsgBoxは
IF msgbox("mmm",vbYesNoCancel+vbInformation,"Title")=vbYes then
とかできますが、これはfnMsgBoxを使うと可能になります。

VBA

Option Explicit
' http://addinbox.sakura.ne.jp/Excel_Tips26.htm
' ただし 原サイトのWin64だと32bitにかまないので、それは外す。
' 上記の確認方法　#IF VBA7 AND WIn64 Thn として#Elseの下のMessageboxWにeを付け加える。Office 2013 32bitの場合関数が見つからないというエラーが起きる
' なおvar = MessageBoxWeとするとdllが見つからないというエラーになる
# If VBA7 Then
Private Declare PtrSafe Function MessageBoxW Lib "user32" _
(ByVal hwnd As LongPtr, ByVal lpText As LongPtr, _
ByVal lpCaption As LongPtr, ByVal wType As Long) As Long
Private Declare PtrSafe Function GetFocus Lib "user32" () As LongPtr
# Else
Private Declare Function MessageBoxW Lib "user32" _
(ByVal hwnd As Long, ByVal lpText As Long, _
ByVal lpCaption As Long, ByVal wType As Long) As Long
Private Declare Function GetFocus Lib "user32" () As Long
# End If
Sub MsgBoxEx(Texta As String, strCaption As String, wTypen As Long)
Dim var
'StrPtr()関数で長整数型（Long）にキャスト
'VBA7ではキャプション、内容ともにLongPtr型にキャストする
MessageBoxW GetFocus(), StrPtr(Texta), StrPtr(strCaption), wTypen
End Sub
Function fnMsgBoxEx(Texta As String, strCaption As String, wTypen As Long) As Long
' 通常のMsgBoxのようにvbYesNoCancel、vbYesNo,vbOkCancelをwTypenに指定する。（vbYesNoCancel+vbInformationもできる）
' 返り値 Long
fnMsgBox = MessageBoxW(GetFocus(), StrPtr(Texta), StrPtr(strCaption), wTypen)
End Function
'MsgBoxEx()関数の使用例
Sub Test()
    Dim Texta As String, strCaption As String
    Texta = "千代田区" & ChrW(&H9EB4) & "町"
    strCaption = "Microsoft Excel"
    MsgBox Texta, , strCaption
    MsgBoxEx Texta, strCaption, vbInformation + vbYesNoCancel
    ActiveSheet.Cells(2, 1).Value = Texta
End Sub