As above.
Images should always have the ICC profile embedded. It's a way of telling programs what kind of data is in the image. It shouldn't matter for the most part. Either a program understands the ICC profile and uses it to ensure the image is accurately displayed, or it doesn't and assumes the profile is sRGB.
From the sound of it you have a bad case of using a colour space which is not sRGB and mixing it with software that just simply doesn't understand it. This is bad on multiple levels:
1) If you send someone your file, how can you be sure they will see it correctly, or print it correctly?
2) If you upload it onto the net ... well most people won't see it correctly.
3) Larger colour spaces sound great in theory but in practice what do you get out of it? Do you have a large gamut monitor? Are you printing your images at the kind of labs which charge in the tens of dollars per picture rather than .30c / photo?
4) Larger colour spaces sound great in theory but the theory also states that for a larger than normal colour space you will need a larger bit-depth to be able to display each colour that is distinguishable by the eye in said colour space. That means no 8bit files, and ultimately NO JPEGs. So if you have a legitimate reason to be using a larger colour space save your files as TIF to maximise quality.