Field aliases can only be saved in the data source in a geodatabase and these field aliases can be exported to another geodatabase, but not to a shapefile. Only geodatabase field aliases will be used when you check the "Use field alias as column header (optional)" button on the Table to Excel tool.
When you set an alias in ArcMap you are setting a Layer field alias that only exists in that map. These aliases are never used by the Table to Excel tool and cannot be exported by that tool.
The only way to preserve Layer Field Aliases is to select all or part of the records in a table view, press the Move to End of Table button to make sure you will output more than 2048 records, right click on the left-hand grey record selector for one of the records and choose the Copy Selected option. Then you can open Excel and hit the paste button. The records with be pasted into Excel and the Layer Field Aliases will be preserved. I just tested this method with 30,000 records and it worked without a problem. However, there are memory limits affecting this option, so at some point this option will fail if your data set becomes excessively large.
This is from the "Understanding field properties, aliases and table display properties" help:
"There are two types of field aliases: feature class field aliases (geodatabase only) and layer field aliases. You work with feature class field aliases in ArcCatalog on the Feature Class Properties dialog box. When a geodatabase feature class is added to ArcMap, its field aliases are used initially for the layer field aliases. However, after this there is no link between the two. Properties set in ArcMap will override the properties of the data source, but they will not be carried back to the data source. This means that if you change a layer field alias, it will not change the feature class field alias, and if you change a geodatabase field alias, it will not update the layer field alias for any existing layers based on the feature class."