Honestly, I have never seen it work.

For me, it's just like any other badge, just for show, just to add to the credibility of the site which could indirectly affect bounce rates/sharing/etc.

There's really no way for them to enforce that policy unless a lot of people squeal about it.

I know here at Moz, it's really something like a Taboo, but it's really not. Big companies do this daily and they do it in bunches.

I would suggest though (since you mentioned that it's just a bitly link) that you just go for it IF the price is right and if it's targeted enough.

Look at it at the standpoint of getting traffic. You mentioned that it's a good site then it probably has a good spot for your link so it can bring in leads. If you can optimize to capture these leads or just get them to your sales funnel, then it'll be worth it. You'll get more links down the line.

It's pretty much like guest posting or paying for a best of the web spot.

Noindex tags and your author page (if you only have 1 author)

For categories, leave it alone, just add a bit of unique content there, much like how ecommerce sites do it.

I would go 404's (and let them die) as I dont think those have any good content on them since it was just generated.

Redirecting them wont really do much.

They will do whatever it is that they already do and their system handles the rest.

Emailing them might work. Sometimes it can change but dont get your hopes up. You can try, then follow up on it. It is yours after all.

If they dont, then be happy with a nofollow link.

Referrals wont hurt

if it was indeed caused by submitting the sitemap, its too late for you to worry about it. My vote, another coincidence. Ive actually experienced this twice and i got my rankings back by analysing where i went wrong with the tech/structure.

With an alexa like that, you probably have a big site. Try to find a "main" problem and fix that first rather than going for different changes all at one time.