Rand, I'm pleasantly surprised to see you mention accessibility in the context of modern SEO. For quite some time I've felt that a certain group of SEO people would make great accessibility consultants (as in hands on experts rather than armchair critics) because what they advocate goes a long way to helping accessibility (as in making sites more amenable to people with disabilities) - it puts in place a great foundation for building accessible websites. I like that aspect of SEO.
The SEO industry suffers because bad and/or over-zealous/self-promoting SEO gains more public attention than a strategy that is well thought-out, considerate and user-centric. Every time someone does a search and the results returned bring up sites a visitor positively does not want to see -- SEO foots the blame more often than not.
I'd suggest the SEO practitioners be seen branching-out and offer services in areas SEO overlaps with others: accessibility, user interaction design, clean copywriting, site monitoring, site metrics analysis, web development best practices, hands-on web site quality improvements, and web user psychology. Even though a lot of this is now fairly typical SEO work, I'd still suggest making it more obvious about the wide range of skills a top-notch SEO practitioner has to offer.
I've come to understand that SEO is no longer just Search Engine Optimisation, but a practice that when done ethically and considerately connects people with the information or service that best meets their requirements. And that involves quite a lot more than convincing a search engine to rank certain key pages for a certain set of keywords.
The common web developer perception of an SEO person is grim. SEO is seen as redundant to web best practice. For a while I considered SEO's main strength - this I gleaned from Danny Sullivan - as the goto person when a web developer fails to do his job properly. I think that's an over-simplification that doesn't help SEO, and the practice of SEO.
I also feel that the top-notch SEO people are too nice. Although the recognise there are elements within the SEO industry that give them all a bad name, they are reluctant to be direct and brutally honest when dealing with bad sections of their industry. In my view, I don't think the SEO industry does enough to throw it's bad people under buses. Bad practices and bad techniques are discussed, but organisations and groupings that are harming the perception of SEO aren't directly criticised. I'd suggest there'd be a cheer breaking out on the web if the SEO industry did a visible clean-up and called out bad practitioners directly (or fisking).
I feel in this regard SEO has earned a low reputation like the Internet Marketing industry. There are some people doing useful and constructive work, but a much more dominant/visible/significant portion just peddling yesterday's snakeoil.
I've been immensely lucky over the past three years to work with some wonderfully talented SEO people in the UK. I find it very interesting to compare and contrast deep insightful approaches to SEO with modern web development techniques and accessibility best practices.
It's not the techniques that have impressed me about professional SEO, but the considered, logical and insightful reasoning behind tailoring pages in certain ways for search engines.
I think that's the sign of a top notch SEO professional. Not just knowing techniques and tricks, but having the consideration of picking the right blend of methods for genuinely improving the site they are working on, their appearance in search engine listings, and bringing the right kind of people to their websites.
I think that's what's so easily missed by people disdaining SEO: SEO is about bringing the right type of people to the right type of sites from search engines. It's finding that balance where a site is listed appropriately to it's real quality to visitors.
A fair number of times SEO is about improving the quality of content on the existing site to justify it's generous rankings -- but we don't hear much of that.
I've watched how the self-identified Black Hat SEO crowd works over the past two years, and frankly I'm surprised how inaccurately they've been portrayed. Ask the typical internet-savvy person about the darker side of SEO and they talk about the dirty tricks of old - cloaked redirects, keyword stuffing, spam. And yet, Black Hat SEO is far more refined than that. It's not the choice of techniques that identifies someone as Black Hat, it's the rationale behind their choices.
To geekily draw a parallel with Star Wars, the Sith have a marked advantage over the Jedi in that they have the choice between using the light and dark sides of the force. The Jedi almost always have no choice but the light side (cue eternal flamewar about Vaapad...)
The strength of Black hat SEO is their ability to quickly and effectively automate techniques that work on increasing their rankings and search engine visibility. So the common routine for these people is to find a technique that improves ranking, and automate the hell out of it, and repeat over and over and over. (Also note, most Black Hat SEO people also keep a squeaky clean White Hat part independently of their darker parts - that's their solid financial base).
What happens is that Black Hat SEO guys right at the fine edge are highly skilled and motivated hacker/programmers - some are exceptional developers. They love solving hard technical problems, that are rewarded in a significant jump in income because of improved rankings. They love the challenge, and it drives them. The perception that Black Hat SEO is just lazy script-kiddies is misleading. I'd suggest that the leading Black Hat SEOers could code the pants off many people, including a lot of talented developers even here. And when Google finds and figures out how to bury their sites they just start again from fresh. They are determined, motivated and self-managed. And they love the challenge of it.
I have a love-hate relationship with SEO. Some stuff makes my blood boil, but every now and again there are moments when SEO practices add loads of value beyond self-promotion. We need to optimise the latter.
(Sorry for the long comment, this is something I've had considerably thought about over the past three or so years)