Given the Hoenn region and the "Emerald" basis for the name, I'm assuming you'll have both Groudon and Kyogre in there at some point.
In which case, I'll share an idea I had - make them a double battle. Since you can't use a Poké Ball unless there's just one opponent (for some reason), the player will have to choose which one to go for. You could perhaps make the other one available later on in the game, if you didn't want to do a "pick one fossil, lose the other" kind of thing. I'm not sure how the weather would work, though - perhaps make it a special battle and have both apply at once (maybe even only for themselves).