Letter of Invitation

Although I think depending on your nationality, you should be able to apply without an LOI, but if you are sure you need, I would suggest you to ask for LOI from govt. approved tour agencies, they will be quick to respond and confirmed to be reliabale. Chk the list in visa section of DGIP (Directorate General of Immigration and Passports) website. Cheers

Yes I am sure I need the LOI as an Australian citizen. I am also an OCI (Overseas Citizen of India).
I have also requested advice from Lost Horizon Treks http://www.losthorizontreks.com/
and await a response. They may be able to provide a LOI.
I could not find the approved tour agencies you referred to:
http://www.dgip.gov.pk/Files/Visa.aspx

Its Eid holidays in Pakistan so you better wait a couple of days for the response.
Lost horizon is also a good option.
http://www.dgip.gov.pk/Files/Visa%20Categories.aspx
Chk section O, although its for VOA for group tourist, yet you can ask them for an LOI for individual cases.

I am also an OCI (Overseas Citizen of India).

This could be a problem. It will take months to process your visa application and the LOI may not help.

Which bus are you looking at that charges 4000 PKR from Lahore to Attari? Take the local bus from Lahore station an you will pay only a dollar or so.

Emeff - Do I need to book for that bus?
Alternatively, is it easy to get a taxi? How much approximately?

Have you come across OCI before? It is not a citizen, it simply allows unlimited entry into India. The processing time given by CIBT is 2 weeks.

bhukari917:
Do you suggest I email the contacts provided requesting a LOI? Will they charge me for it?

How does a LOI from Losthorizontrek or other tour agents qualify my application? How can they accept financial responsibility for me?

yes email number of these agencies, and ask how much will they charge, should be around 50$ or something for just an invitation. As you say you need an LOI, you ask them, they send you LOI and so you have it and your application is qualified to be considered. Actually I don't know the required documents you have been asked to submit by Pakistani mission in Australia, but usually its really easy for Australian citizens to have a Pakistani visa.

I found followings on Pakistan High Commission in Canberra,
http://www.pakistan.org.au/visas.php

Duly filled in Visa Form.
Original passport along with photocopy of passport (of first four pages). Passport should be valid for minimum period of six months.
Two recent passport size coloured photographs (with white background)
Reference letter from your present employer. If self-employed, any document proving your status as such.
Letter of invitation from Pakistan or telephone number & address of contact person in Pakistan.
Personal Bank Statement for the last six months, duly signed & stamped by the Bank.
Travel itinerary.
Addresses both in Pakistan and Australia should be provided.
For minors, both parent's consent duly attested by J.P is required for processing visa for children. Certified copy of child's birth certificate must be provided also.
Persons traveling on Diplomatic / Official passports are required to attach Note Verbal from DFAT.
Any other document(s) that can be helpful in processing of the visa application.
For additional requirements please see the details of required Visa category.
Four tourist visa
If the Visa Officer will be satisfied about the purpose of a visit, appropriate visa will be issued to a visitor or a tourist holding an Australian Passport.
Copy of return air ticket.

So you don't really need to pay for LOI if you have a contact in Pak. Just ask their address and telephone no in Pak.
And if you don't have a contact, make one now, like I did for Azerbaijan Visa. I posted on couchsurfing for someone to invite me to Azerbaijan as I didn't want to pay for LOI. I got invitation for free and had nice stay there. ;)

http://cibtvisas.com.au/

Check CIBT visas, I trust them as I have used them before. You simply elect Pakistan adn get the application pack. In the pack the LOI requires the following:
Letter of Invitation
A letter of invitation from the applicant's host. A copy is acceptable. This letter must:
Include the full address and contact details of the host
Specify the purpose and dates of travel
Include an acceptance of financial responsibility for the applicant
Be dated and signed by the applicant's host
Be accompanied by a copy of the host's national I.D card or passport

As I said, I have emailed Best Western Islamabad and await a response. Hopefully they can provide me the letter free of cost. Alternatively, I have a former colleague in Melbourne who has a cousin in Islamabad who may be able to provide this letter. But if so, how can anyone accept financial responsibility other than the hotel I stay in?

Also, look forward to a response re the taxi cost.
thanks.