NiCad or NiMH batteries, and even LiIon/LiPo batteries, and every other battery out there, suffer from something called internal resistance. Your high capacity made for cameras kind of battery that you paid a lot of money for generally isn't worth the price. The name brand find it in the grocery store battery is made for the general person that doesn't know any better, and truthfully doesn't really need any better. Also the battery packs for RC Cars that come from a Toy store are crap, they weren't designed for a high discharge, they were designed for very low performance cars.
From what you have described you need hobby grade batteries. The kind of battery that you purchase from a hobby store, no not Radio Shack (bad juju) but from a store that sells primarily RC Cars, Planes and Helicopters. Again not Toys R Us or a store that primarily sells other than Remote Control Vehicle products. You can find these batteries online at hobby stores as well (not sure of the best option for Portugal). The batteries used in RC Vehicles are designed for high discharge, high discharge in the effect of several amps used often in less than 10 minutes (less than 5 for RC Helicopters). That goes for all, NiCad, NiMH, and LiPo.
I recommend the hobby stores mostly because it's a much easier way of finding these batteries. They aren't exclusive to the hobby field, but a good hobby store is going to give you a good range of battery capabilities, and they're lowest grade battery should still exceed the common grocery store battery.
I recommend those because of the voltage drop you are reporting. On new, freshly charged batteries your voltage should not drop below nominal. As stated before, nominal is 1.2V per cell for NiCad and NiMH.
As for your Laptop battery........... DO NOT GO THAT ROUTE!!!............ If you are going to use a lithium battery get LiPo in a 2 cell set up, preferably in a flat cell. The battery pack might have some kind of discharge protection, but even from big name brands I wouldn't trust my house, office, my neighbors house with the pack, unless of course the laptop that it was designed to be in was what it was being ran in. Not just the charge, but the discharge.
Currently The vaping crowd (e-cigarettes) is learning about charging and discharging LiXX batteries that the RC hobby world learned about 10 years ago. If you want some nice after pictures of an unrespected Lithium battery go to an rc forum such as RC Groups, and search lipo fire.
Most lithium fires don't happen in the discharge, but the discharge can be the cause.
I am not trying to stop you from using a lithium battery, but want you to use a proper set up. Hobby Grade Charger, with Hobby Grade Batteries.
Flat packs are better than round cells, although the round cells are rigid, they do not compare in capacity and discharge capabilities that a flat pack has.
I have thought about using LiPo's to power a number of items but haven't yet because of the voltage cutoff necessary. It would need to be set up so that at 3.4v or 3.5v per cell, yes they claim 3.1v per cell, but for longevity and safety the higher voltage is much better. For the cutoff it needs to be absolute, ie once it cuts off there is no more draw no matter how small once the low voltage limit has been met. maybe a relay that turns on when you turn on the circuit, and then when the limit is reached it cuts all power? I haven't worked on it yet. You do not want a software switch to turn off the circuit because they draw power even though they "turn off" the circuit. They may only draw a few mAh in an "off" state but they still draw power, and if you don't get to them for a few hours, those few mAh it draws could set your batteries to undervoltage which destroys them (or should for safety).
My resume in batteries is 12 years experience with using them in RC Airplanes and Helicopters, and a little more recently in RC Cars. With proper handling, care, and maintenance I haven't had any of my own batteries fry, although I have seen others lose their entire vehicle in a blaze of glory.