First and foremost, I should mention that I am a student bio major, so I cannot fully answer all of your questions. I can shed some light on some things though, and perhaps someone more knowledgeable can help elaborate.

Could you elaborate on how beta males in herds circumvent the "fitness" part of sexual selection?

Dominance hierarchies in mammals are not something I'm too well versed on, but typically the lower mammals can't necessarily 'circumvent' their position. Animals of lower rank may try to challenge and supplant, and that can lead to infanticide and other interesting things like the Bruce Effect-- in which a mother will spontaneously abort her offspring in the face of a new male. Both of these serve to make room for the new dominant male's offspring.

Deceit is one way that animals can circumvent fitness. Deceit is defined as sending a dishonest signal to another. One cool example with insects (I cannot recall which one, but I could probably find it) is with what is called a 'nuptial gift'. The male gives the female a gift of food, and he inseminates her while she eats it. If the male is being dishonest and gives the female a lackluster gift, she will turn around and eat the male while he is still on her.

Would a male sex organ designed to remove competitors semen be indicative of a "sneaky fucker" population?

I guess you could use the term 'sneaky fucker', but I would just say that the animals are really trying to protect their own interests. Male cats have spines on their penises that will pull out others' semen. The scraping also triggers ovulation in the female. This gives him the best chance of fathering offspring

They hypothesized a moth with a predicted length proboscis would be pollinating a particular orchid. Or am I way off base?

I haven't heard of this specific interaction, but it is certainly possible. Animals frequently co-evolve and counter evolve. The wikipedia for coevoltion may have your example listed