I solved the data validation multiple select issue by creating a small form that I can use to display the values the users need to select.
This method presents other advantages, such as: you can use it on virtually any number of columns, you are able to control how it behaves, allowing you to set the selection as multiple or single, it can also be used to allow users to input free text, and it provides a way for the admin to pass some information, guidance, etc to the users. It also presents the advantage of not being overwritten by users when copy-paste occurs, a problem for the classic data validation feature in Excel.
data_validation_form.png
The example was created in Excel 2010 and I tested it on a 2003 version with the Office Compatibility add-in installed, without getting any errors.
Please find attached the example and detailed explanations of how to use it.
P.S.
I only posted this solution because the ones that I came across didn't solve the problem for more than one column and I thought it might help some people out.
DataValidationForm.xlsm
DataValidationForm_howto.docx