@grumpazoid one thing I meant to add..
The way you propose, using a battery and regulator is the ideal path. Removing the LED is critical as the LED would probably use more power than everything else.
One thing you may not realise is the Arduino and motion sensor can run on as little as 1.8 volts, providing all regulators are removed and the battery starting voltage is no more than 3.3. If you use an alkaline battery, you can suck on those babies until they reach 1.8 volts, at which time they are pretty much empty. Whereas rechargeable lithium batteries have builtin 'over-discharge' protection which switches off the output a 3.[something] volts.
I suggest considering 2 by 'AA' cells in a holder, with the Arduino mounted on the back of the holder with double sided sticky tape, or my preference where size is important is to use one CR23 (3 Volt) battery (they are about 2/3 the height of one 'AA' ). Either option should give you over a year between replacement.
NOTE: On ALL MySensor nodes, make sure the antenna section of the (standard) RF2401 is not directly on top of anything metal. Where possible, let that antenna part overnang the battery pack for example. It's not critical, but could cost you 20% to 25% of your range IMHO, so I try to keep it clear wherever I can.
I've seen it argued that metal behind the antenna, can act as a 'ground plane' and actually boost range. I'm certainly not a radio expert, but even if that is true, it will make the antenna very directional, meaning signals to/from behind the 'ground plane' will be blocked. All I can say is I haven't had any range problems will any of my nodes, including some in another building.
Whatever battery arrangement you use, measure the voltage of a fresh set of batteries (in use), and make a note of the voltage when the node dies. This will then give you the useable voltage range which may be for example 1.83v to 3.12v. Once you know the usable range, you can then modify your code to calculate and send a very accurate "Battery Remaining %". In the meantime you can just guess the 'empty' voltage.
p.s. You don't have to wait a year, you can just put in a fairly 'empty' set of batteries just to see the point at which the node dies, if that makes sense.