I had the same problem originally. I found that if you watch the guards carefully they will patrol in patterns. You can search when the high level guards are at the far end of there patrols and you can search without being involved in any battles at all.
Now this may not be as fun for some but for others being sneaky is the way to go.
I was able to avoid the guards and get all the things at the fort without a fight.
