単純に考えれば、状態によってコマンドを置き換えるより、コマンドが実行された時に
状態を調べて処理をかえる方が、MFCの仕組みから考えて簡単。
OnXXXXCommand()
{
if (GetKeyState(VK_SHIFT) & 0x8000)
{ OnPrevios(); // 前へ
} else
{ OnNext(); // 次へ
}
}
ツールバーを押した瞬間とキーボード状態を検査するタイミングにほんの少しタイムラグ
があるけど、実質は問題ないでしょう。

この方法ではツールバーに紐づけされているコマンドそのものを変更しているわけでは無い
ので、キーボード状態でコマンドのイネーブルコントロールしたい場合、OnUpdateXXX()も
同様な処理が必要になります。

上記は、作る立場からの意見。
使う立場から考えると同じアイコンを押してキーボード状態によって動作が
異なるのは不親切。動作が異なるならば、ユーザインターフェース（見た目）
も変えて欲しい。
ということで、シフトキーのON/OFFでツールバーのビットマップも変更する
のが良いのではないでしょうか。
# 実際にはやったことが無いので、コードはなし！

CToolBar::SetButtonInfo()を使えばできるでしょう。

切り替えは、ON_UPDATE_COMMANDUIハンドラのタイミングで
行えば良いと思います。

BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
ON_UPDATE_COMMAND_UI(「前へ」コマンドのID, &CMainFrame::OnUpdateXXXX)
ON_UPDATE_COMMAND_UI(「次へ」コマンドのID, &CMainFrame::OnUpdateXXXX)
END_MESSAGE_MAP()

void CMainFrame::OnUpdateXXXX(CCmdUI* pCmdUI)
{
int image;
UINT id;
if (::GetKeyState(VK_SHIFT) & 0x8000)
{
image = 「前へ」ボタンのイメージインデックス;
id = 「前へ」コマンドのID;
}
else
{
image = 「次へ」ボタンのイメージインデックス;
id = 「次へ」コマンドのID;
}

int index = m_wndToolBar.CommandToIndex(pCmdUI->m_nID);
UINT style = m_wndToolBar.GetButtonStyle(index);

m_wndToolBar.SetButtonInfo(index, id, style, image);
}

補足です。

メニュー等にもコマンドを割りつけたときのために以下の
処理を追加しといたほうがよさそうです。

void CMainFrame::OnUpdateXXXX(CCmdUI* pCmdUI)
{
int image;
UINT id;
if (::GetKeyState(VK_SHIFT) & 0x8000)
{
image = 「前へ」ボタンのイメージインデックス;
id = 「前へ」コマンドのID;
}
else
{
image = 「次へ」ボタンのイメージインデックス;
id = 「次へ」コマンドのID;
}

int index = m_wndToolBar.CommandToIndex(pCmdUI->m_nID);
if (index < 0) // <-- 追加
return; // <-- 追加

UINT style = m_wndToolBar.GetButtonStyle(index);

m_wndToolBar.SetButtonInfo(index, id, style, image);
}

普通に両方のツールバーボタン作っておいて
シフトボタン押された時と離れた時に
CToolBarCtrlのメンバ関数で
HideButton(ID_NEXT,TRUE);
HideButton(ID_BACK,FALSE);
とかで片方だけ表示する
ってのはどうでしょ？

やはり、メニューとツールバーには別IDのコマンドを割り当てておいて
ハンドラの中でメニュー用のハンドラを呼び直したり、
両方のコマンドをツールバーに入れて
動的に入れ替えられるような機能を作るいうことになりますか。

CMainFrame::OnCmdMsg()の中で状態によってnIDやCCmdUI::m_nIDを書き換えて
再帰コールという方法で行けないかなと考えていたのですが、
この方法が安全なのかも不明ですし、皆さんに提案していただいた方法を
既存のアプリにうまく組み込めるか調査してみたいと思います。

ご意見ありがとうございます。