First, consider that even domestic transfers used to be slow and expensive in most countries not so long ago (and they probably still are in a few places).
There has been some incentive to optimise those for a number of reasons:
cost reduction for banks: they do prefer fully automated fully electronic transfers to paper cheques that need to be processed more or less manually, scanned, etc.
competition: credit card companies have taken a relatively important share of payments due to the convenience of those payments (which seem to happen immediately, even if it's a bit more complex than that).
regulatory pressure: especially in the EU, where directives have forced banks to be able to handle bank transfers in 24 hours even though it used to take days before.
But domestic transfers use mostly national banking systems (exceptions in the EU again with SEPA). Those systems are optimised to handle huge numbers of transactions, in a single currency, with well known bank account number formats, a single set of laws and regulations.
As soon as you get out of that:
- volumes drop significantly, especially if you consider each country pair
- you're faced with multiple banking systems
- you usually have the additional layer of the SWIFT network
- bank account numbers are often not standardised, so there can be needs for manual processing (this is getting a lot better with the introduction of IBANs in many countries).
- there could be specific regulations in either country (currency controls, reporting obligations, various additional checks)
- banks don't have a relationship with all other banks. They often have to go through other banks (correspondent banks) or central banks, which need to be paid as well.
There's also the issue of currencies. Currency exchange is a complex thing, you need to buy currency when you need it, there may be complications (sometimes you need to go through a third currency). Add again regulatory restrictions.
It makes it a lot more of a "custom" product, so it often remains expensive and slow. Also, in many cases, banks want to keep a simple pricing structure, so even if transfers to some countries are much simpler/high volume than others, they have a tendency to apply the highest cost to all. And since those transactions are a lot less frequent, customers have a lot less incentive to switch banks just for a one-off payment here or there.
Now, in come the new players, ranging from Paypal (not so new nowadays) to Transferwise. They are often a lot less expensive, and usually a lot quicker, than banks. But there are limits to what they can do. Over the last couple of decades, there have been lots of additional checks all financial institutions and payment providers have to make (KYC, PEPs, etc.), in theory to fight financing of terrorism, in reality to fight money laundering and tax avoidance. There are limits on how much you can send before they check and double-check who you are, where the money is coming from, where it's going to...
They also need a license in both countries, be connected to the banking systems in those (if you money is in your account with them in the destination country but you can't get it out, it's of no use to you...).
A final note on paper cheques: if you send a national paper check to someone in a different country, that is going to cost them a huge amount (if their bank is even willing to accept the cheque).