To delete all evolution settings:

rm -r ~/.evolution
rm ~/.gnome2_private/Evolution
gconftool-2 --recursive-unset /apps/evolution

Evolution stores all the account information in the gconf registry, but the cache stuff in .evolution.