All newer phones use Lithium polymer batteries.
Why is it Partially Charged?
To decrease their aging they are intended to be stored at 40% charge. This means when you receive your phone it should be at 40% charge, otherwise they will have aged your battery for you. (you are probably used to the effects of aging, like a 2 year old phone seeming to have very short battery life). When you get your phone you can use it until it is discharged, but they normally say 'charge it' because people will not notice the partial charge.
Do Not Fully Discharge
You should not fully worry about fully discharging, this is superstition to earlier battery technologies. Fully discharging a lithium battery is one of the best ways to make it fail. below a certain charge they will have their overcharge protection circuitry fail and you cannot charge it at all. I have seen studies that show that this makes up more than 75% of "failed" lithium batteries.
Lithium Battery Aging
Lithium batteries have a set number of charge discharge cycles before they fail. This might be a number like 500 cycles. You actually get more like 1000 cycles if you only discharge to 50% before recharge. Lithiums really do not like a deep discharge, I cannot stress this enough.
If you would like more information about lithium battery technology let me know, I can get you many links, just drop me a comment. I have a few answers on the electronics and robotics stack exchange about it.
Can I leave it plugged in all the time?
Yes, and no. This is very dependent on whom makes your device.
For example, my Lenovo laptop will not apply a charge to the battery unless it is under 97%. When it does charge the battery it charges directly to 100%, then stops until the battery sags below 97%. Many laptops did not do this, on most just applying charge if it is not 100%. This would put the battery through thousands of charge cycles in a week when you are not using the battery. This ages a battery quickly.
If your phone maker took the time and paid the extra cash then your phone will stop charging once it reaches full charge and just power the system from the wall outlet. It is significantly more likely that your phone is charging your battery on a short cycle and aging it thoroughly.
Myths
Some people have some confusion from some of the myths that go about. The primary one is memory. As Battery University will say, this is mostly extinct, and actually applies to nickel-cadmium batteries. As was stated in a comment about crystals Battery university has in reference to nickel-cadmium:
With memory, the crystals grow and conceal the active material from the electrolyte. In advanced stages, the sharp edges of the crystals penetrate the separator, causing high self-discharge or electrical short.
Now, talking about Lithium batteries, which your phone uses, there is even more difference. To quote them battery university directly from their simple guidelines:
Avoid frequent full discharges because this puts additional strain on the battery. Several partial discharges with frequent recharges are better for lithium-ion than one deep one. Recharging a partially charged lithium-ion does not cause harm because there is no memory. (In this respect, lithium-ion differs from nickel-based batteries.) Short battery life in a laptop is mainly cause by heat rather than charge / discharge patterns.
I understand how this may go against what you have been taught, but I am someone who not only has research this but uses lithium batteries in my day to day work as an engineer.
Batteries can only supply a given amount of current. You could use an adapter that supplies the same voltage and exceeds the current capacity of the batteries to properly power the device.
I would recommend using a current meter to simply measure what the device uses: Get a 3X AA battery holder, and insert your meter between the batteries and the lamp. Measure with fresh batteries and you will have your current usage. An adapter that exceeds the value by at least 10% should suffice.
If your device has a DC power jack that isn't labeled, you will have to investigate as to whether the tip or ring is ground. Obviously any adapter you purchase could be modified to match a given polarity; many have plugs that can be attached either way. (I personally solder my own using adapters that come with bare wires.)
Make sure you get a regulated power supply. An unregulated one can supply more than 4.5 volts if not powering the load it was intended for.
Best Answer
A device (phone) gets charged at optimal (high) rate only when it recognizes "charging port signature" on charger side. For Type-A port, there are several DIFFERENT port signatures that a charger port can provide:
USB Battery Charging v1.2 Dedicated Charging Port, where D+ and D- are floating but tied together;
USB Battery Charging v1.2 Charging Downstream Port, when a special low-voltage handshake over D+ and D- lines happens;
Apple charger signature, when a combination of DC levels is present on D+ and D- lines with high-impedance resistor dividers (75k/50k);
Sony charger signature, when D+ and D- have 5k/10k dividers to VBUS;
Qualcomm "Quick Charger" signature, which uses an intelligent IC on charger side to understand a special sequence of DC levels driven by device on D+ and D-; can provide 9V and 12V on VBUS;
Samsung charger signature (details unknown, to me);
USB Power Delivery protocol V1.2 - uses complex packet-based protocol over VBUS wire using FSK modulation method at 23.2MHz carrier frequency. The port might have additional contacts to detect plug insertion.
...
For Type-C connector, there is a newer Power Delivery protocol v2.1, which solely uses the CC wire (Communication Channel) to negotiate voltages and available currents that can be delivered via VBUS.
A charging port usually provides only one signature, and most of mobile devices have an intelligence to recognize it, usually by sequentially probing different signatures. When a phone recognizes something it understands, it will take the charge. [However, there were attempts to make a charging port that tries several signatures sequentially, as some Microchip/SMSC hubs of the past.]
We don't know what kind of signature is used in this particular power bank, so all bets are off. Now, consider that your old phone can be designed for some other proprietary signature, so it should not come at any surprise that some phones will not charge well (or at all) from this particular power bank.