You can only get Deoxys on Birth Island, but you can only get there with mystic ticket that is given to you on a Nintendo promotion. You can now exactly how in "www.pokemon.com/deoxys".
Once you have beaten the Elite 4 you will be able to get the national dex from oak and to capture johto pokemons and see hoenn pkmn (you can't them except for deoxys)
There are 9 islands, (you can only get to 7 of them, (one is deoxys one and the other is where ugia and ho-oh are(need another ticket from a promotion)) you can go to the 3 firsts islands when you defeat cinnabar gym lader, blaine. bill will come and tell you if you want to go(it doesn't matter if you say "no" cause he will wait on the PC until you want) You must save a girl and in 1st island is mt. ember, where moltres is, don't worry if you don't catch, you can go there again at anytime later. the others islands you can go once you have beaten elite 4. There are Johto pkmn.
This time you don't have to buy a lemonade or water, in celadon mansion an old woman gives you a TEA. when you pass through the guard, he will ask you if he can have some and then you can go.