The show-stopper concern is the tax country. For example, there's a few jobs advertising as "US/Remote", this does generally mean they will only consider hiring into their office in the US or remotely working from the US.
This is especially valid with the established companies. Startups and smaller gigs might just hire you as a consultant, so that they don't have to deal with the taxes for you. This would be a somewhat flakier job security, in my opinion.
It gets way easier in the EU. Once they've an office in the EU, you should be okay working from anywhere else in the EU, AFAIK.
Another important concern you've already nailed: experience working remotely. This may be substituted with the proven ability of working without supervision, so at certain seniority level shouldn't be an issue.