I've only recently discovered that the mystery egg even existed. I went to the police station with a growlithe and talked to everyone there but there was nobody who wanted to trade with me (I also did the same thing with a growlithe egg). I've finished episode 16 and the city is now rebuilt. Were you only able to get the egg prior to you entering agate?
I'm pretty sure that your're not supposed to break the wall, the gate should be open. Try downloading the latest patch (patch 10 I think)
When you download the patch folder it should come with 3 more folders. There will be folders in the rejuvenation folder with the same names. Replace the patch folders with the rejuvenation ones (keep the old rejuvenation folders just in case something goes wrong)