It's really hard to hit him sometimes, even when I'm beefed up with AD and Attack Speed. Why is this, and how can I counter it?
The main reason shen takes so little damage in trades is because his W skill, Feint, is a shield. Essentially this adds to his hp every time it comes off cooldown. In order to help damage him, you can make sure to hit him as soon as his shield disappears and is on cooldown. It's a bit tricky, but manageable. Damage dealt when his shield is on is reduced by the strength of his shield.
Another reason you might be dealing less damage than you expect is because of the damage reduction effect of his E skill, shadow dash. Taunted champions deal 50% reduced damage.
Also, Shen gains very high HP regen after hitting a unit he has marked with Vorpal Blade. This lets him regain health lost to harassment much quicker than most other champions.
The final reason you might not be dealing as much damage as you want to is shen's defensive items. If shen is stacking armor, then he is also going to take less physical damage. The solution to this is building armor penetration, such as Last Whisper or Brutalizer, or simply taking more armor penetration from runes.
Assuming that your question means it's hard to deal damage to him, you should build a last whisper after you're beefed up wtih AD and ASPD. This is because Shen is a taking who will more than likely have high amounts of armor, which causes your physical damage to be reduced by a certain percent. Last whisper counters this by getting rid of 40% of the armor he has, which means he reduces less damage.