I am doing a combination of the two. I have crated a large structure that has a hole in the bottom center towards the right of center. This is to look like a cave, and the tank wall (painted black) will show through. I put rocks along the edge of this opening as ledges to further produce the cave look.
The foam adds a substantial amount of structural integrity to the plastic eggcrate. I do not think I'd do just eggcrate and rock. I have about 25 pounds of rock on mine (65G tank) including an arch (flying buttress is what it really is) and even without the eggcrate trimmed, it was incredibly flexy. I used zip ties and mostly buried them in the foam, as I too did not want to see them, but wanted as tight of a structure as I could get.
Once the foam is on, you can cover it with epoxy and sand or crushed coral to make it look more natural. I even bought salt for water softeners and sprinkled that over the foam after spraying it and allowed the foam to harden with the salt there. Now I need to wash the salt off, and it should leave the foam with more jagged edges, which will look even more realistic once covered in epoxy and crushed coral. I'm using the Bob Smith Industries 20-minute finish resin from a model store in Wallingford.
I have to start a build thread for mine, but everyone wants pix, so I've been collecting pix as I go and will load up the pix when I start the thread. Just wanted to give you an idea of the massive flex in the structure as you are proposing, and a way to make the foam disappear immediately instead of having to wait a year for the foam to be completely covered in coralline before it blends in and "disappears."