I consider SEO as part of the design of projects I consider, I don't consider it a service or something I might hire someone to do, but then my perception is that outsourced SEO means spamming links around. I admit I may be ignorant and maybe you can enlighten us.
Patrick is a member of the excellent seobook.com community, which is also a great source.
I would have thought one would need to do well over low 6 figures to justify such an expense.
Edit: I see Patrick is a moderator, so I assume it is a "barter" deal.
BCC does substantially in excess of $3.6k a year due to advice I got from Aaron. YMMV.