I'm trying to beat the game for my first time with my HuFi and my runs are pretty consistent due to being a Fi but it seems Ecumenical Temple is a bit hard to find. I already know that it can be found between dungeon levels 4 and 7, it just seems so elusive and difficult to track down. Is there any strategy to find Ecumenical Temple or to track it down and make sure you haven't missed it other than to autoexplore and try all the stairs?
The strategy you have detailed is the best way to ensure nothing has been missed. Ensuring you have fully explored the level and have gone up and down all six staircases into a level (three from the level above and three from the level below) will allow you to find the Temple.
(I don't believe the Temple is ever generated in a non-connected part of the dungeon, as I do not recall ever not finding it. I haven't checked the source code lately, though...)
However, I do question why you are so concerned with finding the Temple, especially as a player learning to play Crawl. While it is a good early stash location, if you want to worship a god, it is far better to pick a character that starts off worshipping a god so that you accrue piety from the very start of the game.