I know the guy will be at the outskirt stand but I have beaten the game and he isn't there.
You can't. Togekiss is a Gen 4 Pokemon, which Colosseum did not have.
Edit, as you seemed to have changed you question...
It can be at Outskirt Stand after you purify all 47 Shadow Pokemon. A guy will be there trying to impersonate you.