Zum "Pfalzgrafen bei Rhein". Das Grimmsche Wörterbuch schreibt im Artikel "bei":
Bei und an, bei und zu berühren und vertreten sich oft, wer bei dem berge, steht auch an dem berge; die stadt liegt am Rhein, beim Rhein
Leider kenne ich mich mit dem Mittelhochdeutschen nicht gut aus, das "bei Rhein" geht jedenfalls auf mhd. "bi rin" zurück. Später wird man den Titel einfach mit "bei" weiterverwendet haben, und das heute verständlichere "am Rhein" hat sich dann nie durchgesetzt, das "bei" sich als Anachronismus im Gegenteil sehr lange gehalten. Zumindest "beim Rhein" anstatt "bei Rhein" wäre dann allerdings schon zu erwarten gewesen im Laufe der Zeit.
Aber die rheinischen Titel sind ja ohnehin eine Sache für sich. Überall sonst haben sich die Grafen nach Burgen o. ä.benannt, nur die am Rhein schrieben sich "Raugrafen", "Wildgrafen", "Rheingrafen"...