|Found the solution.|
For Excel 2003:
Select all images using the "Select Multiple Object" button and then Delete.
This "Select Multiple Object" button is found in the Drawing toolbar, but is not initially enabled. Make the Drawing Toolbar visible (View -> Toolbars -> Drawing). Then to enable the button, click the Toolbar Options (small droplist arrow at the end of the Drawing toolbar) -> Add or Remove Buttons -> Drawing -> (check) Select Multiple Objects.
For Excel 2007:
Select all images in the "Selection Pane" and then Delete.
The "Selection Pane" is found in:
Home -> (Editing Group) Find & Select -> Selection Pane
This will list all Images. I can't find a way to select all in the list but I can Control Right Click on each one and delete afterwards.