I suppose a good way to do this, for the bad guys, is to have everyone be invisible, and to have a silence effect in place (that's just about to wear off). So, they pop in, but no one sees or hears anything.
If the bad guys did this, I'd still require that the rest of that round (i.e. the bad guys' move action if the teleporting was the standard action) be spent re-orienting.
But, during that portion of that round, I'd make Listen and Spot checks for the PCs (don't have them roll, they'll know something is up). If anyone gets a high-enough Spot check, they might notice a ripple or disturbance in the air, akin perhaps to an out-of-place heat wave. If anyone gets a high-enough Listen check, they might notice that there's a peculiar lack of sound in a certain region.
If a PC made such a roll, I'd say something to the player, or hand him a note. If the player says something like "Hmm. Well, I'll walk over there and see what's going on," then they're surprised. If the players says something like "I draw my sword and prepare for battle," then they're not surprised.
Everyone who isn't surprised will get to roll Initiative, of course, the rest will have to wait a round.
Dave