Você tem a regra de reescrita distorcida.
RewriteRule ^\+([^*]+)/?$ /cgi-bin/shop/shop.cgi/$1
significa que quando o cliente navega até a página mysite.com/+, seu servidor agirá como se tivesse escrito mysite.com/cgi-bin/shop/shop.cgi/
.
Se você quiser que uma reescrita funcione na direção oposta, será necessário trocar a expressão e o alvo, assim:
RewriteRule /cgi-bin/shop/shop.cgi/(.*) /\+$1 [L,R]
Isso significa que, se o cliente navegar até mysite.com/cgi-bin/shop/shop.cgi/FOO
, ele receberá um redirecionamento para mysite.com/+FOO
Por favor, note que não é uma boa idéia usar a regra atual e esta ao mesmo tempo, já que corre o risco de causar um loop infinito, pelo menos se você estiver usando redirecionamento, já que o redirecionamento causará um novo pedido que será novamente analisado pelas regras de redirecionamento.