The Most Excellent and Right Honourable Doug Avery tries to clear up the mysterious Save for Web color shift:

This comes down to a matter of taste. As you can see, Row 4 [sRGB, no embedded profile] produced great, predictable results as long as you remember to turn on Color Proofing while you’re viewing things (and in CS3, it’s off by default every time you start Photoshop). This indicates that sRGB is workable, you just need to be careful that you understand what you’re seeing.

I still prefer the monitor profile [no embedded ICC profile] (Row 8), it simplifies the entire process and makes my results even more predictable. It also might makes things easier if you’re in a hurry and need to mix screenshots into a comp without the colors mis-matching.

Click the link, view the poster, pick your poison, and never have an issue again.