visas are fine, everyone knows what one is.
visa-waiver-program is a special case for the US only, in that it's not a visa, but it still kinda is. However it's almost a different word entirely, if it was just called some acronym, say (VWP) we'd have used that, so I'm still happy keeping the long version.
visa-free-entry - um, what? Oh right, for places that don't. Why not just stick with [visas]? Some questions will be 'Do I need a visa for X given I'm from y?', and others will be 'I'm from y, so I don't need one, right?' and although it's esesntailly the same question, they're going to try and do different tags if you allow both visa-on-arrival and visa-free-entry. I'd keep it in one place for now.
OK, let's revise. Now that I've spelled that out, I'll rephase with my preferences:
visa-waiver-program is special, and I re-iterate that it needs to exist. Perhaps as a synonym to something else. I'll come to that.
visa-required should be a tag. This can be used to determine whether is required before getting there.
visa-on-arrival should be a tag. This is for arriving and getting a visa at the border, instantly. visa-waiver-program should now be added as a synonym for this, but should definitely still exist.
visa-free-entry - I don't like it, but thinking about it it makes sense to keep.
Other tags related to visas which should stay: schengen, eu, free-travel-zone etc. No need to add them if they don't exist, but that sort of thing should be kept for people to search on.