Toysoldier,
I'm going to treat each question in two parts; one for a private pilot, the other for a commercially certificated (or higher) pilot.
Situation 1:
Pilotman wants to use his airplane to carry the pastor from point A to point B. Pilotman pays 100% of the expenses.
A private pilot, or a commercial pilot may do this, within limits. If there is any tangible commercial reward in any shape, even though costs are not being accepted by the pilot, it may still amout to flying for compensation or hire, even though it doesn't cross into the charter arena.
If the flights are conducted for the purposes of accepting tax breaks, and for bolstering one's professional reputation in the community by obtaining publicity, for example, a case may be made that the flight has been performed for compensation. However, my opinion is that the FAA would be stretching the line to make the case. I don't have any case law to refer you to, as there are still too many variables.
In substance, if Pilotman wants to make the trip, and it is at his suggestion, and he invites the pastor, and pays for the trip out of his own pocket, there should be no issue with legality. The trip is legal. If the pastor approaches Pilotman and asks for a ride, and pilotman had not intended to make the trip anyway (in other words, if it's a special trip for the purpose of transporting the pastor), the case may be made that the logging of flight time is compensation. There should be no difficulty here, says logic. However, holding out can be an issue, and if the pilot provides the airplane and the pilot services, it can become a private carriage certification issue. (you can see where there are still variables that can affect the outcome of this question).
A little more specific information is needed.
Situation 2: Pilotman wants to use his airplane to carry the pastor from point A to point B. The Pastor pays 100% of the expenses.
Unless Pilotman is operating under a Part 135 certificate, this is clearly a no-no. For a private pilot to make the flight, he could pay a pro rata share (50/50 if dealing flying only with the pastor), but again he must be careful to ensure that the flight is his idea, and that he cannot be placed in the position of appearing to hold out for the flight. Even as a commercial pilot, holding out while provding the airplane to transport someone can put someone in a real bind.
A commercial pilot is not obligated to pay a pro rata share when splitting costs, but in this case, it's the minimum he could get away with and make an effort to appear legal. Again, this is assuming Pilotman's own personal airplane. At issue is Pilotman providing the airplane and the pilot services.
It should be clear here that even if Pilotman buys the airplane and sells half to the Pastor, he can still run afoul of Part 135 by providing the pilot services for the trip (legal interpretations are available to support that).
Situation 3

ilotman rents an airplane to carry the Pastor from point A to B. The Pastor pays 100% of the expenses.
Same as situation #2. Pilotman is providing the airplane. Private or commercial, if he is providing the airlplane, he's in a position of being close if not over the line into Part 119 and 135 territory. The specifics of the situation make or break his legality here, and not enough information is provided.
If Pilotman is flying from A to B on Saturday and invites the Pastor to come along, okay. He should still pay the pro rata share of the expenses, even if commercially certificated. Paying any less will appear to be a charter operation.
If the Pastor requests transport on Saturday, and Pilotman rents the airplane for the purpose, he's providing an illegal charter. If he then compounds the issue by allowing the pastor to pay for the entire operation, he's in deep doo-doo.
Situation 4: The pastor makes arrangements with the local FBO for an airplane. He then asks pilotman to fly him from point A to B in the rented airplane.
Much better, now. The real issue here isn't so much one of legality, as weather or not the FBO will rent the airplane to the Pastor. Normally, the person it's rented to will be the pilot in command, or the person exercising operational control.
Here's the rub, however. If Pilotman works for or is in the employment of the FBO, it's tantamount to the FBO providing the airplane and pilot, and the situation again runs afoul of Part 135. The FAA has taken the stance that employment doesn't necessarily mean a regular paid employee. This throws another wrench in the works. Even if the FBO isn't paying the pilot to make the trip,and even if the FBO isn't connected monitarily to the pilot, the case may still be made (depending on circustances) that it's an illegal charter because the pilot is still working for the FBO.
To clarify that, imagine that the pilot is an independant instructor there, or a check airman in their Part 135 school...or a designated examiner who is used by the FBO to test students. Approved in any way, by the FBO (and this can include a checkout for insurance purposes). Under the FAA standard, that person is still in the capacity of an employee of the FBO, and the operation may be construed legally to be an illegal charter. Tricky, I know, but the FAA has taken that stand before, and it's supported by legal interpretation and case law (don't have the time to dig that up right now).
Situation 5:The church owns an airplane and asks pilotman to fly the pastor from point A to B. The church pays the expenses.
If the pilot is a private pilot, it's a problem. If the pilot is a commercially certificated pilot, he can do it. He is now no longer being paid for conveyance or transportation from A to B, but for acting as pilot in command of the airplane. The big difference here is that he isn't providing the airplane. He may even be an employee of the church, or a congregation member...doesn't matter. He's not providing the airplane, only pilot services.
If he's a private pilot, he can't advertise, even by reputation or word of mouth If he's commercially certificated, he can advertise all he wants.
Situation 6:ABC Company owns and operates a part 91 aircraft. ABC Company uses the airplane to fly the pastor from point A to point B. The pastor pays for gas only while the company donates the remaining operating expenses.
No can do. See the legal interpretations above. The company can receive no reimbursement, without requiring an operating certificate.
When you spoke to differnent FAA personnel, did you speak to them at the FSDO level? You're very likely to get different viewpoints there, but it's important to note that it's opinion, not an official representation of the position of the Administrator. My comments alone don't represent that, either, but are a summation of certain legal interpretations and case law. I should add the caveat that I have no legal standing, nor authority in any way, shape or form. When I get a moment, I'll try to add the other information so you have a solid reference to go by.
I just glanced back at your message, and you said it was the Washington office. Never the less, without an offical legal interpretation, the office can only provide an unauthoratative opinion. What's really needed are the interpretations and case references. I'll add some when I have a little time, and I apologise for the delay.
The interpretations above are a good start.