Nah no dialup, we've both got cable, although mine is wireless but I have a 6dbi booster for my card and another booster connected to the router itself. We've toyed with Hamachi for other games but were never able to get it to work, never actually tried it for SC though.
The lag really is bad, but I think it's all me. I usually can't host games without people getting the latency error, but I can join other people's games fine. Once the game actually starts there will be intermittent lag throughout or sometimes it'll just slow down to a crawl for minutes at a time. The weird thing is we play Warhammer Dawn of War all the time with no lag issues whatsoever, and I believe both games use port 6112. In Warhammer I'm able to direct connect to him though, using his IP.
I've got DMZ enabled for my computer, I've forwarded all the ports, added exceptions in the Windows Firewall. Some days we can play lag free, a lot of times we can't. Most of the time we just play against computers, but every once in a while we'll try a random 2vs2 and it'll lag like hell until the other guys leave, then when it's just us left the lag will settle. But then again I think we've gotten an occasional lag free 2vs2 game going, I dunno, I honestly think Bnet is just a hit or miss pos.