I would use Computed Fields. Store and display user input with spaces, but index and search computed field too.
These computed fields are populated with values that you define via PHP code.
So you can simply remove white spaces, or re-format phone number in any way you please, and store a standardised copy of user's phone number without them. That way both representations will be searchable.
As a small bonus, other modules (like Views, various exporters and connectors or phone integration) would be able to benefit from this too. And you'll be able to export valid vcards easily. Bad thing is a slight overhead on reads and saves.