You can do the "paste into address bar and re-copy" dance. I'm getting pretty fast!

CMD-C CMD-T CMD-V CMD-A CMD-C CMD-W CMD-V

If you're using chrome, the omnibar seems to send out whatever you type to (google's?) server for search suggestion, so you shouldn't do that if you're copying sensitive data. You can use ⌘+shift+v to paste the text without formatting (and without sending your data to some random servers).

I used to do this until I learned CMD-SHIFT-V which pastes without formatting so the text appears in whatever format the destination document uses

That's exactly what I do every time, and I became unnaturally quick in this insane dance.

I also find this frustrating. For applications where it happens frequently, you can map paste/paste-and-match to keystrokes you can remember using System Prefs > Keyboard > Shortcuts > App Shortcuts. There isn't a global change you can make without 3rd party tools, AFAIK.

For frequently-used shortcuts that have hard-to-remember modifiers, I change them to the full set of shift-ctrl-opt-cmd so that just mashing my hand across the entire corner of the keyboard will get the job done. Has the nice side effect of (usually) avoiding the unexpected overwrite of other default app shortcuts.

Can't you put it under "All Applications" to have it take effect in all apps?

Yes, but it will break Cmd-V as "Paste" on apps that don't have a "Paste and Match Style" option. :(

I use Plain Clip (https://www.bluem.net/en/mac/plain-clip/) which is a tiny application which will remove formatting from text in clipboard. It's meant to be triggered from a hotkey / launcher app like Alfred or Spotlight. One plus is that you can set preferences to remove extra spacing or new lines.

My occasional workaround has been to paste in a text editor as plain text. I agree though, that the paste and match style should be default.

Just cmd+shift+v pastes without formatting ... which is often just whatever is in the target. The explicit 'with formatting' paste is hard to remember though.