I've beat the bosses in Wonderland, Deep Jungle, and Agrabah, even defeated the 3 headed dog and the Phil Cup. My walkthrough says that I should head to the right of Agrabah and then be swallowed by Monstro. The problem is when I head that way I always end up at one of the worlds that I've already visited before. Have I missed something here or not completed something?

I've tried that, and many other different routes, for a whole week now and I'm still getting no where. I'm so frustrated!

Right, it's been like three, probably even four years since I played the original Kingdom Hearts (I got it when it was first released, so no Final Mix or whatever it's called).
Anyway, I've found a couple of guides, and the only thing I can think for you to do is this:

Have you got the Battle Level 5 World, or Level 5 Battle World or whatever it's called, available to the right of Agrabah? If so, then select that as a destination and auto-fly, if you can, to that location, or, if you can't auto-fly there, then fly normally. Anyway, on your way to Battle Level 5 World, or whatever it's called, Monstro SHOULD automatically appear in space and swallow your Gummi Ship.

That's really all I can say. There's no real trick or anything, it just happens automatically.
As far as I know, you don't need any specific Trinity Limits, or Spells before you can get swallowed by Monstro.

Have you got ALL Trinity's, Spells, and Summons up to this point? If not, then maybe try going back for one's you've missed. Apart from that, there's not much else I can suggest.

(meh, Im a newb...) Ive locked Agrabah but I still cant go to the level 5 planet to get swallowed by Monstro, Its so frustrating! How do I get to it?