Cannot choose different cellular network while on roaming

I am an EU citizen visiting a different country now (but still in EU), in the country's capital. For my travels I have bought a data pack from my provider (I don't have/use data otherwise). Now whenever I turn mobile data on, I only get EDGE connection. My provider's helpline assured me that the data pack I bought is supposed to be 4G. It is a major provider in my country and on the helpline they claimed that 4G should be available in the area I am visiting right now. They have advised me to manually select a different local cellular network. I tried to go to the Settings, Mobile Network and choose the network manually -- I saw that there were several 3G and 4G networks from various local providers around me with a good signal strength. However, whenever I choose a network to connect to, the connection fails (it says Unable to connect under the network name) and I get a system notification from Phone Services *(or is it Cellular Services? Sorry, my phone is not in English)* which claims: No signal. The chosen network ( (xxxxx)) is not available (where the x's are always a different number, depending on the chosen network). The only way I can connect to a cellular network is to choose an automatic connection in the Settings but it always connects me to EDGE. I have also verified that my preferred type of cellular network is set to 4G/3G/2G. My phone: Xiaomi Mi A3, Android 11 (Android One). The SIM supports LTE. Do you know what could be the problem and how to solve it?