Something I found out recently is the results of Void Summoning varies with the Luck scale. Therefore, I see Luck+3 as almost required for any Rlyeh strategy that plans to use the Void Gate.
This leads to two other benefits. First, you get your Heroes very quickly. This is good, because at least two of them (the Aboleth and the Traitor King) are powerful mages. The other benefit is, if you can get a Nature/Blood mage, you can use Crossbreeding. As you point out, Rlyeh makes better use of fodder than most.
A Sloth scale is possible, but I generally don't take it. I like the Meteorite Guards too much for that.
My normal preference is to take a Temperature scale, since they don't affect underwater.
As for Voice of Tiamat, while nice, I prefer using Acashic for those who can easily use it. And Rlyeh is arguably the people with the easiest time of it.
For me, I see Rlyeh's bane in Pangaea. Even their Satyrs have like a 13 MR, which sucks for the illithids.
Anyway, just my 2 yen.