So I take it back - one can store web part properties with web parts. I was missing the WebBrowsable property - that seems to do the trick. From Ted Pattison's book, Inside WSS v3 - good reading indeed!
private string xmlUrl;
[ Personalizable(PersonalizationScope.Shared),
WebBrowsable(true),
WebDisplayName("Feed Url"),
WebDescription("Set your RSS feed's XML URL here!")
]
public string XmlUrl {
get { return xmlUrl; }
set { xmlUrl = value; }
}