IIRC, P360s use C/HC series logic, which is specified to be tolerant up to 6V and are only recommended for use up to 5.5V. 7V could cause damage.
Most wall warts do tend to run high with no/low load. You can try finding one rated for 4-4.5V or adding an artifical load, aka big'ol resistor. A 100 ohm 1W resistor (or two 220 ohm 1/2W in parallel, purchasable at Radio Shack) should bring the wart down nearer to 5V.
There are some nicer wall warts out there that don't run high like that. These are the "regulated" kind. Some are based on a 60Hz transformer followed by a linear regulator while others are switching type. Either should run much closer to the voltage on the sticker.
Another option would be to use your own voltage regulator. A 7805 and a couple caps should work, especially at low currents like those needed to run a P360, but they always need a few volts of overhead, so you may need something like a 7V rated wall wart.
Stealing from USB should be fine in this application. Include a 100mA fuse and a series diode on the VBUS line (1N4001-1N4004 or similar is fine). VBUS is specified to not exceed 6V ever, so you should be good.