Visual Studio の発行オプションは、アプリケーションをスタート メニューに追加していないようです。
Windows フォーム アプリケーションを 1 つ作成して公開しました。(VS 2008)
ウィンドウの [プログラムの追加と削除] に公開アプリケーションが表示されますが、[スタート] メニューには表示されません。
公開設定で「アプリはオフラインでも利用可能(スタートメニューから起動可能)」にチェックを入れました。
また、公開された EXE ファイルがどこに行くべきか。私も見つからないので。
Windows XP を使用しています。