I believe that whatever picture you add to an Excel File (or Word Doc for that matter) it is stored as the same internal format (unfortunately it's a .bmp i.e. uncompressed).
This is a common mistake with people with fancy cameras, they think (because they can) they should insert a 10M pixel image, this is rarely the case. Think about it, if your image is part of a report and you print it off and the image is 2 inches by 3 inches then even at 300 dpi (what ALL commercial photo printing labs print at) you'd only need 600 x 900 pixels i.e. 1/5 MP not 10 MP. So reducing the image size should be your first step, your second should be as bob suggests to use the best compression you can for the image as despite what I said earlier the document also stores the original (more file bloat), then as you say use the compress ALL images option (though if you've done as I've said you probably won't get much out of this).
If you DO NEED to include 10MP images then you are doing things wrong.
What you'd need to do is employ a developer to write something that will open the 10MP image (that was sent with the file, but not in it) in either a common desktop app or in a form to display the picture.
Edit : I often cheat and instead of using 300dpi images I'll use 150dpi and thus quarter the file size.