Yes, deleted data can still be stored in the file & recovered by a 3rd party to whom you send the file. Most word processing and spreadsheet programs preserve deleted data for some time; this data is part of what's usually called "metadata" -- data you don't see. This is true even if you are not tracking revision history; this is the data that is used, for example, when you "undo" an edit.
One way to remove metadata is to convert the file to another format and back again, as Al Everett suggests.
This is a detailed explanation from MS about metadata in Excel, but it is a bit dated: http://support.microsoft.com/default.aspx?scid=kb;EN-US;223789 . The concepts still apply to later versions.
In Excel 2007, you can use the "Document Inspector" feature to clean up metadata. There are details on what this feature does at http://office.microsoft.com/en-us/excel-help/remove-hidden-data-and-personal-information-from-office-documents-HA010037593.aspx#BM1
Usually, the easiest thing to do to remove just revision-related metadata (i.e. deletions as you mention) is to just save the file using "Save As", to a new name, and use XLS format if you currently use XLSX. This -should- remove all the revision metadata but will not remove other items like your name etc.