I believe the answer can only be empirical, not definitive.
To examine some of the figures mentioned:
there is a 20% inefficiency (which I do not know if it is true for most portable charger)
A portable charger that is itself charged from USB (5 Volts) would need a boost converter to be able to supply 5 volts at its output. Boost converters commonly mention efficiency of 65 to 85%. TI's TPS61030, TPS61031 and TPS61032 state 96%, and Maxim's MAX8815A states 97% efficiency.
These figures do not account for possible efficiency loss due to external components (ESR of capacitors for instance) or temperature variation. Thus, treat that "20%" number as indicative at best.
your phone needs power for stand-by, so in my experience, you'll have just 65% capacity.
That would depend on whether the phone is kept powered on while charging, what power intensive tasks (e.g. WiFi, social media polling software) are running on the phone, and even the current draw of the phone in the nominal "powered off" state - Some smartphones do not actually power off completely unless the battery is pulled out.
Thus, that 65% number is also indicative at best, though varying it somewhat is within the user's control.
by industrial standards for batteries is +/- 20% tolerance admitted with capacity.
That number would be defined in the datasheet of the specific battery in question. It would also vary widely by age / charge cycle history of the battery, temperature, contact oxidation and possibly several other factors.
So, while the number is a reasonable guesstimate, it is not definitive.
Note that this last figure is applicable to both, the cellphone battery and the portable charger battery.
So, can one use the magical value 45% as a gauge for portable battery charger?
Clearly not. The only numbers that can be used, even as a rule of thumb, are those empirically measured for your particular situation and use pattern. Even so, the percentage will change widely over charge cycles, season and time of day (temperature factors).
1: Yes, you can do that. Essentially, that's how power supplies work. They can handle multiple parallel networks within their current capacity. As for the heatsink, that depends on the regulator, the current draw, the ambient temperature, how efficient it is, etc. It's not a simple yes or no.
2: The capacitors depend on the regulator as well. Some require them all the time, some only require them depending on the input or output conditions, some never require them. The NTE1960 you linked to does not have an extensive datasheet, but is pretty similar to the LM7805. The capacitors are pretty much required for stable use. But these are linear regulators. Not efficient and they convert wasted energy into heat. Going from 12v to 5v, at say 700mA which is the high end for the RPI, that means 12 - 5 = 7v * 700mA = 4.9 Watts of energy being converted into heat. A heatsink would be required.
A Switching regulator is more efficient, in terms of both energy and heat. The OKI-78SR component you chose is a Switching Regulator. It shows that it would not need a heatsink in that same situation (Not in the engine compartment though, that's a different story). It is also a complete module, including the capacitors and the resistors it needs. It would be better.
3: A Car USB regulator would work just fine for your case, as long as the draw on it is under it's maximum. Some are 500mA, some are 1A, or better or in between, but some can't actually supply the amount of current it says it should, so you would need to test. The Model B has a 700mA draw/limit, the Model A is 500mA. Most of these usb regulators are switching supplies, and for your purposes, a car usb adaptor would be exactly like the OKI-78SR. At 4 bucks for the OKI-78SR (plus shipping) compared to a few bucks for a car USB adaptor, it really just depends on which you can get easier. Even retail, you can get a decent car one at any convenience or auto store for 10 bucks.
You could even gut the car USB adaptor for the board inside. Those things are so small now they are smaller than a car cigarette lighter, with the case, and the size of an SD card without the case.
Best Answer
You don't mention what case style of 7805 you have. If i was guessing you are using a TO220. That case can only support up to 1A output current and even then requires substantial heat sinking to do so. Some 7805s had thermal protection and would shut down if overheating. Check the voltage to the device when it shuts down. Perhaps the voltage drops out.
Also you cryptically say that it's a 5v device. If i also had to guess it's a USB device. Some USB devices require that an identified is detected on the data lines to announce that the device is connected to a charger. For example my HTC phone charger shorts the data lines together. Also my Galaxy tab doesn't like my HTC charger because Samsung uses a different scheme to identify the charger.