First I'll answer your specific points, and then I'll give my own take at the end.
[The title] likely appears everywhere - whether company email address books or your email signature or on your resume.
Regarding corporate address books and emails -- depends on the company. Some might specify only your offical title, others might let you put whatever you want. Your resume, however, is your own. You can put whatever title you want. If your official title was "Member of Technical Staff" but your role was actually being a project lead, go ahead and put "Project Lead" on your resume.
From my experience, your title can oftentimes affect how receptive and prompt other employees are to helping you or answering your requests (for example "Engineer" vs "Manufacturing Engineer" vs "Senior Engineer" vs "Development Program Engineer" or even "Intern" vs "Product Engineering Intern" etc).
This depends highly on the industry, the company, and the person to whom you are talking. The banking industry has a highly stratified pecking order, of vice presidents no less. There are Junior VPs, Assistant VPs, Associate VPs, VPs, Senior VPs, and Executive VPs. (I think those are in order. I might have missed a few.) What's more, people at different banks seem to care whether they're talking to an SVP or EVP. On the other hand, in high tech, titles are commonly "Engineer I", "II", "III", "IV" and so forth, and nobody really cares.
How receptive others are to your requests depends on a myriad of factors. I think that the title is in the noise. Furthermore, providing a puffed-up title is likely to be counterproductive. If somebody comes to me and throws their title around, I'm more likely to think, "What's this guy full of?" (But that might just be me.)
Additionally, a title becomes part of your personal brand for better or worse, considering how often the title is associated with your name.
I really don't see this. At big companies the title is usually assigned, and usually nobody cares. If they do care, it's because the title is an indication of one's rank (such as in the banking industry) but not one's brand.
I know a guy who puts "Evil Genius" on his business cards. It's pretty funny, and he's a funny guy, and that's part of his brand. But in no way is that his official title, either. Your personal branding comes from things other than your title.
1: Is a job title a negotiable element of an entry level position at larger companies?
Mostly not. The title is often linked to pay grade, and if you're entry level, pay grade is tied pretty closely to education level and work experience. If you have reason to believe you're being placed at the wrong pay grade based on education and experience (e.g., all the Bachelor's degree holders are Engineer I, and you're offered Engineer I, even though you have a Master's) then you should negotiate your pay grade on that basis, not the title.
2: Should you attempt to negotiate a title when the title may hinder your efforts at the company, such as indicating you are in a development/training program?
If you don't want to be in a development/training role, then you should decline the offer or ask to be placed elsewhere. If you're accepting a development/training role but you're objecting that your title has "intern" in it, well, that seems misplaced. If someone is introduced to me who has "intern" in their title, I'm more likely to help out, educate, and mentor that person than otherwise. I can see how some people might decide they don't need to pay attention to an intern. If your title doesn't have intern, though, they'd pretty quickly size you up and decide you didn't deserve the attention anyway. It's the person you're dealing with, not your title.
3: Can negotiating a title be a way around a "we only pay $X for new engineering employees with title Y" or simply allow better salary negotiation?
No. See answer to #1. Title follows from pay grade.
4: Is having a unique/more specific title a positive or negative, assuming the title has meaning outside the company as well?
If the industry has generally recognized titles (such as VPs in banking) then you're best off having one of the standardized titles. If the industry doesn't have titles that apply across companies, they're mostly meaningless and can even be the opposite at another company. For example, at one (high tech) company I'm familiar with, basically everybody was Member of Technical Staff. (There were several grades of MTS.) At a different company, the grades/titles were Engineer I, II, III, IV, but only when one got promoted beyond Engineer IV did one become Member Of Technical Staff. So, if the industry doesn't have generally recognized titles, they're pretty much meaningless across companies, regardless of whether yours is unique or more specific.
In summary, it sounds to me like you're placing too much importance on the job title. Far more important is what your role actually is. Is it interesting? Will the experience enhance your career? Is there opportunity for advancement? These are a lot more important to your career than a title.
There's no Permanent Record somewhere of your official job title. Most are bland, and generically descriptive. As such, nobody cares much about them. In some industries a title is an indication of rank, but if you don't have the rank, you don't get the title. In other industries (high tech? software only?) some companies allow one to choose one's own title. This is usually played for laughs. ("Evil Genius")
If you're having difficulties dealing with other departments, it's almost certainly not because of your title. It could be a political struggle between the department directors; it could be something about your communication style that's not conducive to eliciting the desired response; it could be that the other department is just so busy that they don't have time to respond to anyone, not just you. Some of these issues you can do something about, and some you can't. Either way, worrying about your title won't affect anything.