Indeed, my method is very time consuming. But I am still developing it, and
hope to make it more efficient. (For instance, I have not really
established what the optimal time control is to play these games. I am
using 40/2' with fairy-Max now, and 4/1' for my better engine Joker, but
it turns out that Joker finds the same Pawn-odds score at 40/10' as at
40/2'. If that would be true for all scores, I could speed the process up
by a factor 6!)

I currently have one dual-core PC entirely dedicated to Chess testing
(running 24/7). And I consider fairy-piece values one of the spear points
of my research. I have too many spear points, though: I develop two Chess
engines, micro-Max and Joker, also in variant versions, am currently the
main contributor to the WinBoard open-source GUI (and in particular the
only one that cares about variant support). I want to write a Shogi
engine, and develop a much faster end-game-tablebase builder. I could use
an extra computer, but I want to postpone my next buy until I can get an
8-core Nehalem. Because I want to develop a new SMP algorithm for tree
search that scales better on large numbers of cores, and I really needs a
machine to test this on. So for the time being, I will have to do with my
2.4GHz Core 2 Duo.

But eventually I will do most fairy pieces. I will probably convert Joker
to handle fairy pieces as well, as it can reach the same quality play in a
fraction of the time. If you have a computer (which is likely, since you
post here), you could easily do such tests yourself too, however. It is
harder on the PC than on the tester! It is just a matter of letting it
run, and once a day look at the result, set up a new position and start a
run for that.

I am currently running a test with 2 Ministers against 2 High Priests
(starting at the A and C positions of Capablanca Chess, so in a context of
all normal Chess pieces). This seems a pretty even battle, In fact, after
62 games, the High Priests are even leading (26+ 22- 14=, 53.2%). I guess
I will let it run overnight. But they are very close, so the High
priestess is also more a Rook replacement than a Bishop replacement. My
Rook opening value on 10x8 is only 475. So 625 is even on the strong side
for a Rook. (Why do you find that surprising? A Rook on 10x8 has a MAXIMUM
of 16 moves, and most will be blocked on a non-empty board. All 16 moves of
Minister and High-Priest are unblockable.)

I have not tried your leaper replacements for Bishop and Rook yet, but
some time ago I very precisely tested a similar piece, F+D, because I
wanted it to investigate pair bonuses for color-bound pieces (and F+D is
color-bound). A pair of these pieces tested nearly as strong as a pair of
Knights, perhaps a quarter Pawn weaker (this was on 8x8, though). This
would make it 290, as my Knight is 300 on 10x8. I don't know yet,
however, how much of this is pair bonus. But if a color-bound piece with 8
unblockable moves can be wrth as much as a Knight (at least, in a pair),
the non-colorbound pieces F+A and D+W must be similar or better, and thus
good Knight replacements.

It is funny that a pair of the F+D, which is the (color-bound) conjugate
of the King, is worth nearly a Knight (when paired), while a non-royal
King is worth significantly less than a Knight (nearly half a Pawn less).
But of course a Ferz is also worth more than a Wazir, zo maybe this is to
be expected.