Some receivers (the box at the sound booth) have a volume control. It may be that the difference between the Shure and Sennheiser is that one of them has a volume control turned louder or quieter than the other.
Are there monitors on stage? If so, does the feedback go away when the mic is moved offstage? Is the mic intended for singing, or speech only? Maybe you need to take some of that mic out of the monitor(s) if used for singing; take it completely out if used for preaching (the pastor doesn't need to hear himself in the monitors).
Is the feedback high frequency or low frequency? If it's mostly low frequency, cut everything below 100 Hz on that channel (the lowest people can speak or sing is about 80 Hz, so you won't be losing anything). Many mixers have a "low cut" (sometimes called "high pass") button to accomplish this.