Do you have the tones (noises) turned off? That speeds it up alot...
As for 4gb micro...
this is where i bought my last one...
http://www.emartbuy.com/usa/ecatalog...=506&storeID=1
ebay is usualy safer if you can find one thru all the crap on there:
http://cgi.ebay.com/4GB-Micro-SD-HC-...QQcmdZViewItem
WOOT!