There's a thread with answers from WotC's support that say that when you gain concealment from the Warlock's shadow walk, that you can stealth immediately as part of that. You can stealth as part of any action, so long as you end with cover/concealment.
Remember, that if you succeed in your stealth check, that just because they don't know where you are it doesn't mean they don't know where you are.
If you're hidden in the only square in the room that provides cover/concealment, then they can still attack you with a -5 to attack. It's a 5x5 square with stuff in it, and they don't know exactly where within it you are. If you succeed well enough on a stealth check in a room with lots of places of cover, then they have to guess which square you might be in. It balances pretty well.