Hmm... someone posted issues with search before, but we could never figure it out. Are you running on the latest version of Ubercart?

On the Livetest, when I search for orders with billing first name "ry*", "RY*", "ryan", etc. I pull up any orders for Ryan Szrama. Same with last name. Direct and wild card searches are matching. I'm not sure what would be causing it to screw up for one site and not another unless it was a bug that was fixed somewhere along the way.