I hate to suggest Rio competitors on this board, but have you looked at the latest "SlimX" model from iRiver?

http://www.iriver.com/product/info.asp?p_name=iMP-550

It's got rechargeable NiMH "stick" batteries, but also some kind of external battery pack that accepts regular AA. If the former works like you described the SP250 did, then it seems like the best of both power options....