On the other hand, it seems that if I were to start an encounter in stealth and move past an enemy, so long as I passed my stealth check, he could not gain an Opportunity attack...
In a combat scenario, you cannot simply walk past an enemy and maintain the Hidden condition - as soon as you attack, or break from cover, you are seen. However, you do keep the benefits of being hidden for the duration of the single action that reveals your location - this is how attacks hidden from cover, or the use of Deft Strike (a single action move+attack) can gain you Combat Advantage and thus Sneak Attack bonus damage.
That rule would equally apply to a single Move action taken to get past someone, meaning you could indeed run past someone and not trigger AoO if you started your turn hidden from them - however, you would not still be Hidden from that enemy at the end of that Move action.
It is also possible to be Hidden, take a Move action to move past someone and end up in another position where it is possible to use Stealth skill to hide from them - and roll Stealth to hide again.
If you can, find a way to maintain stealth whilst moving close to the enemy. At low levels, that might be cover or concealment very close to the enemy (imagine a room full of furniture with the rogue hiding behind it, or a half-closed door, dark shadows etc - but the important thing is that the DM rules the items give cover or concealment affecting the enemy). If you can find these, you can move around a foe without risking attacks of opportunity, and without losing your Hidden condition (well, provided you don't attack anyone)
Bear in mind though that many enemies are not stupid - once you are revealed after the first time, the enemy will have a good idea of where you are even when Hidden and can use their action to e.g. walk around the cover, find you automatically and attack you, or use an area-based attack where they don't even have to see you. The Hidden rules in 4E can get quite complicated in this regard and take a few times read through, ideally with DM and stealthy player discussing them. On the plus side, if you follow them carefully they do work nicely in 4E's tactical system, and can be a lot of fun.