Is 'chercher' a specific kind of 'search' en français? Not 100% sure why it cant be used in this sense?
Not "Il fouille dans ton sac/votre sac"?
It may be used with or without "dans".
That was my immediate reaction too, but "fouiller une voiture" (search a car ) is what the police do, whereas your suggestion I think would be more "He is rummaging in your bag".