In answer to your second question, the two solders are pretty close to the same, it's really dependant upon what's in it and how big it is. I tend to stay away from any acid-based rosin core flux, because it's messy on you're board and slowly degrades your soldering iron tip.
I can't say how much I highly recommend an organic water based rosin core flux. It's clean and seems to work really well, but as you've probably noticed it's more a matter of opinion. I believe Kester is a popular solder manufacturer and can be bought from most dealers. I tend to stay away from radio shack type solder, becauase again the thicker the solder, the more heat required. Something on the order of .015" or .02" is really nice to work with. and stay away from anything silver based. Some of that solder melting temp is like 1000F.
In regards to the recommended temperature and different tips and what not, it again will depend upon who you ask. I work for Lockheed Martin and they have very strict soldering procedures that are basically dictated by NASA and as I said most of the industry follows this. There may very well be tips that support 700F to 800F and even higher, but these are generally for more industrial style applications, where you are soldering huge terminal lugs which 10 guage wire or the like.
The MIL-SPEC or military specification for soldering temperature is right around 598F or 600F (for electronics and PCB's) if you will and the time alloted for soldering tip application is on the order of 10 seconds or something, which is actually a little high. I've seen parts (mainly delicate IC's) get damaged when a technician is trying to desolder the part.
I'm thinking that most of the equipment you have is just fine for what you're trying to accomplish, especially if you are really ramping up the heat, but ultimately it sounds like the board you're trying to solder is just competely sucking up all the heat being applied to the pin.
Just out of curiosity, if you examin your through-holes or vias if there are any, does the little copper plating have any breaks in it. Depending upon whether the board has internal planes or even top and bottom layer copper pours for GND sinking, if the board isn't using thermal relief holes (looks like a little wheel with spokes), then it could theoretically never solder well.
I know none of this actually solves you're problem, but as a test of your equipment you should think about by a simple perf-board and try soldering some random resistors to it, with the correct temp and what not and see how it goes. It could be a sign that the PCB board is the problem.
[EDIT] And just a note, you can always tell if you are exceeding the temp of your solder if upon cooling it is a dull grey color and not shiny silverish looking. In this case you have exceeded the temp and have created a cold solder joint. I also agree about the last post on putting a dab of solder on the tip, while not in use but still kept hot. This does help prevent oxidation, but that is typically cause by the acid-based flux (or rosin core) in most solder.