> Does anyone else recall seeing the word "genii" as the
plural of genie? I thought I'd seen it in an older book,
but can't verify it now.

It seems to be more appropriate as the plural for 'genius'. Like the plural of Radius is Radii.