1) If it's not a Bad Egg, then it could just require a large amount of time.
It would be helpful if you could tell us in which route did you got it.
2) Technically, I feel as if the end was the Orange Archipielago, since what comes later (Mirage Tower and Sevii Islands) feel more like a post-game content.
3) To start a side quest you just go to talk with NPC/s depending on the side quest.
I know it's a vague description, but I'm having a hard time to find the correct words to explain it myself.
Go and speak with Nurse Joy in the Pokemon Center.
That's one of the reasons as to why Beta 11E savefiles are not compatible with Beta 12, Aethestode mentioned in
this post from 9 months ago or so, that he got to expand the amount of Items in the bag.
Catching Mewtwo is technically optional.
Go back to Valencia Island and surf all to the right and north.
(Also, you get a Master Ball by completing a Sidequest in Celadon City, just saying)