I believe the max. external memory the 4000 can address is 4 megabytes. The manual may report this. In real life I have found that a 1 or 2 MB card is way more than enough for hundreds of presets.
You don't need rechargable cards. I only happened to advice you that brand because I have a rechargable one they made. The advantage is that you'll never need to buy and change an internal battery. The downside though is that the card should be inserted in the +powered on+ unit to be recharged. If left in the 4000 for long time, without powering the unit off, it may be completely discharged. My experience with these cards is 100% positive though. Never had a single problem as I had with other brands.
all the best