I ended up replacing my 720 battery last month and am posting up these pictures I took, based on recommendations by dhn. I am in no way stealing credit for this thread at all, but just thought I would post my pictures of my procedure to add to the thread.
Finally decided to order the battery for real and replace it. All went well. SUPER easy! Removing the battery was very easy as well. The trick is to lift the battery up just enough so you can get your finger under it, and then slowly let it start lifting up on its own while pulling up in a super steady motion. Do NOT try to pry the battery up at once. It will slowly start coming off on its own with while keeping even pressure. It's nothing more than super super super super sticky TAPE..ish stuff. At least that's what was in my device.
Do NOT use anything metal to remove battery. Use any hard plastic object. The battery I bought came with an entire tool kit for free! Here are the pics of the process

and here is the link to the auction I got my battery from.
1300mAh Li-Polymer Battery w/tools for TomTom Go 720 - eBay (item 370324154424 end time Apr-21-10 20:31:11 PDT)
I bet this battery will last a WHOLE lot longer than when I first got my TomTom since I bought my 720 refurbished, and the original battery never did have that great of battery life. Back then, my 720 wouldn't last anymore than 2 minutes unplugged right before I replaced it. It's recommended that you fully charge and discharge the new battery about 2 or 3 times for the first charges so the battery becomes conditioned. After conditioning, I got about 3 hours of use on a full charge WHILE playing music via the FM transmitter the whole time and while driving with the TomTom. The TomTom/battery hit 4+ hours when simply sittng idle in my bedroom without any routes planned and without the device moving at all. Here are the pics!
If you have any questions, let me know!

Sorry if the pics are too big. I can "try" to resize them even smaller but it would be a pain since there are so many. I originally took these pictures at 15 Megapixel size which made them HUGE!!!!

If you really would like them resized then let me know.
^^It is MUCH easier to pull the battery out vertically. Didn't have to bend a single thing. Again, just pry it up enough with the plastic pry tool and stick your finger under the battery and slowly let it peel itself off. ^^
^^Very sticky stuff, but not hard at ALL^^
^Very sticky!!!^
^^Heat gun to stick the new battery on^^
Post continues below on next post due to the number of picture maximum per post.