I have always trusted her.
“von je” seems like an odd way of saying “always” here… is it archaic? I would have expected something more like:
Ich habe ihr schon immer vertraut
Ich habe ihr seit ewig vertraut
Or even just: Ich habe ihr immer vertraut
It is indeed odd. “von je” is a variation that I have never heard. I can’t decide if it’s archaic, sublime, or just odd.
Other variations include “seit je”, “seit jeher”, and “von jeher”. Personally, if I were to use “je”, I would have used “seit jeher”, but you’re right, the alternatives you have listed are much better (but see below).
Duden.de says this about “seit jeher”:
Die Fügung seit jeher ist aus einer Zusammenziehung der Fügungen von jeher und seit je entstanden. Deshalb wird sie manchmal abgelehnt, und es wird empfohlen, sie durch eine der beiden anderen Fügungen zu ersetzen. seit jeher wird aber nicht nur häufig verwendet, sondern ist auch durchaus korrekt.
So “von je” is neither of the mentioned variations. Maybe that’s why it sounds odd to me.
But dwds lists “seit, von je”, so that’s at least a confirmation that “von je” does exist 
As for your alternatives, somehow the second one (“seit ewig”) does not sound right to my ears.
Better alternatives are “schon ewig”, “schon eine (halbe) Ewigkeit”, “(schon) seit Ewigkeiten”, or “(schon) seit einer (halben) Ewigkeit”.
But then there are google hits for “seit ewig”, and there’s the common phrase “seit ewig und drei Tagen”. So let’s just say “seit ewig” is at least not as common as the others.