There's a few apps out there for stuff like this, as the Quick Search Box is a little limited and the in-built contact managers seem to fail at this too (at least HTC's People does)
Try
Gesture Search, if you find it easier to draw numbers than to type. It's fairly flexible and free.
Contact Lookup does this too and it's free though ad-supported if you use the application rather than QSB. It supports either mode. (blatant self promotion, sorry).
If your numbers are formatted with spaces, brackets, etc, then Contact Lookup Pro or Contact Lookup Fast will find it by ignoring the formatting. They're paid apps.
Alternatively,
Contact Search+ does it too, though only via the QSB. (recommend a competitor product, balance restored ;-) )
Then there's the uber search tools like
Power Search that search everything on the phone, not just contacts.