Are you guys trying to create matches instead of join them? I had a lot of trouble joining them, similar to the problems you guys had - it seems like the severs are authenticating several people into the same slot, and only the chosen one gets in. But every time I've created a match, it took no more than a minute, usually about 10 seconds, before someone else joined my session.
Doesnt change the fact that the online game is still rather silly. I've now gone from a 1-10 W/L ratio to a 10-1 W/L ratio. How? Taki. The answer is that simple. Theres no finer combination of speed and range to exploit the online lag like taki. Better yet, I've created the beefiest, brawniest, least taki looking custom fighter, and gave him taki's style. No one seems to expect the astaroth looking dude to come out swinging like taki, and when all else fails, I guarantee you that mashing A and B in succession as fast as you possibly can will win you the match far often than not.