This isn't really a Cisco problem.. it's an exchange search problem.
 
Since it's a text field, your users can enter whatever they please in Exchange and basically screwing you. There are two ways to make it work:
 
1) You institute a policy that say E.164 numbers only for every number... then at least for national numbers you can be reasonably sure you'll find what you're looking for.
2) You load all the contacts, reformat the number (replace +, strip spaces, strip dashes, remove brackets, etc.) then compare that with the number you get from JTAPI.
 
My caller identification application contains both mechanisms and I can activate whichever I need depending on what the customer is willing to do (the first approach means quicker lookup but potentially more work for the user, the second approach means no work for the user but a longer lookup time - the way I've implemented it I load the contacts upon the first lookup, then cache it for a day, and only perform additional lookups for numbers I don't find in the contacts I have in memory - of course that ends up using quite a bit of memory if you're dealing with a lot of users but that's the tradeoff).
 
If only Exchange allowed for SQL functions, right? Doing DB lookups you can sidestep the issue by having an SP that reformats numbers during lookup so you can really search for