マップの検索履歴が削除できません。

iCloudの設定で「マップ」をオフにすれば一応履歴は表示されなくなります。

ただし、iCloud上には履歴は残ったままで、設定をオンにすればまた履歴が復活します。

macOS上のMapでも同じように履歴の削除ができませんので、iOSのバグというより何かiCloud関係のバグのような気がします。

>どうやって報告すれば良いのでしょうか？

最初に書かれたように、マップの履歴を削除しても勝手に復活すると書けばよいだけだと思います。

なお、ここはユーザ同士の情報交換の場であり、アップルは書かれた内容を公式には見ていません(ここでバグ報告しても開発部隊には伝わらない)。フィードバックページに書かれた内容は開発部隊に伝わります(対応するかどうかは先方の判断次第ですけど)。

iPhone X, iOS11.2.1です。

同じ症状ですね。バグかな？

iOSのためのマップ - フィードバック - Apple（日本）

にフィードバック(バグ報告)しておいたほうがよいかも。