Thanks for the help, I created a rewrite rule for that:
RewriteCond %{REQUEST_URI} ^(/duty-free-shop/produkt/.*)/(category_pathway|related_product)-[0-9]+$
RewriteRule .* %1 [R=301,L]
The breadcrumbs do not really matter because the structure used is very flat and there is no need for the categories to appear in the breadcrumbs.
Anyway, I don't see the reason, why related products should anything have to do with the breadcrumbs; that solution/feature seems kind of strange because it assumes a hierarchy between two related products. A config-option to disable that would be nice.
(If anybody has the same problem and wants to use the above solution, you have to substitute the part "/duty-free-shop/produkt/" to your site configuration [the first being the shop-menu-item-alias, the second the SEF-URL-configuration-value for products in Hikashop])