Edit: BrandonMTurner has a better writeup http://news.ycombinator.com/item?id=3457973
The former is "hard", since even though you might not want the user around in the present, you usually want their history to persist. However, the latter case is comparatively simple. If a spambot posts on my wall, then yes, emphatically, delete that wall post when you delete the spambot. Delete any photos they uploaded. Nullify all their votes/likes/plus-ones/whatever. Make it so that the whole thing never happened, other than perhaps as a line in an abuse log.
It is critical, though, that this should never happen automatically in a case where an automated account might be confused with a human one. It probably shouldn't even be exposed as part of a bulk "check off these accounts and purge" moderation view. But in cases where the automatedness of an individual account is out in the open and there's no contradictory evidence whatsoever, the "tactical-nuke" button could be a viable option. (Whether you can trust your community's moderators to not misuse this button is a whole 'nother can of worms.)