おっしゃるとおり、ギリシャ語「パラドキサ」を日本語に直訳すると背理, 逆理, 逆説となります。 一方「パラドキサ」は、英語「パラドックス」の語源でもあり、こちらが名前の由来だと思います。 パラドックスの意味をざっくり言うと、突き詰めると2つの物事が食い違い、つじつまがあわないという「矛盾」のことです。 パラドキサカレハカマキリも、定義の上では成り立っても、実際にはありえないカマキリであることから、学名がついたのでは ないでしょうか。