SUBSTITUTE(Q3, " ", "")
is not validating the cell, it is changing it.
One way around this (if you must achieve this using Excel datasheet functionality) is to have a "dummy" column hidden away somewhere that does the transformation, then point your validation formula to that cell.
For example Formula for Cell["AL3"] is
=SUBSTITUTE(Q3, " ", "")
and your validation changes to
=if(LEN(AL3)<15,"True_Thing", "False_Thing")
You could have many hidden columns, each performing a specific validation, then your final validation would be (for example)
=AND(AM3, AN3, AO3)
Or do it in VBA where you can apply as many validations as you choose ...e.g. see
http://stackoverflow.com/questions/409434/automatically-execute-an-excel-macro-on-a-cell-change[
^]