Google+フォトは Picasaウェブアルバムをベースにしている写真共有システムです。
Google+フォトに写真をアップロードするとその写真は Picasaウェブアルバムに反映されますし、Picasaウェブアルバムに写真をアップロードするとその写真は Google+フォトに反映されるようになっています。
したがって、Google+フォトで写真を削除すると Picasaウェブアルバムでも削除されているはずです。
問題はスマホに同期された写真だと思います。
もし、サーバー側に写真が無くてスマホ側に残っている場合は ギャラリーのキャッシュをクリアしてみてください。
もし、それでもダメならギャラリーのデータの消去を試してみてください。