Yo se que unos posts mas abajo hay un tema del 2009 hablando de esto mismo, pero ya intenté la solución del caché y no funciona para nada.

Para ser específicos, lo que no se actualiza al instante son los archivos css y js que uso, los archivos php y páginas con el mismo formato muestran los cambios instantaneamente.

Que debería hacer para solucionar este problema, la espera para que se vean los cambios puede durar hasta horas

Puedes hacer una prueba... quita un archivo css, entra en la web y comprueba como afecta el cambio, después pon el archivo css nuevo y vuelve a entrar ¿ha cogido ya el fichero nuevo?

Quito el archivo y el cambio no se ve reflejado en la web, es como si el archivo siguiera existiendo, lo vuelvo a subir y sigue igual sin los cambios que había realizado

Eso es por el cache de tu ordenador o de tu conexión a Internet. En este punto presiona CTRL+F5 y mira a ver si se nota que falta el archivo.

Misma situación, como si siguiera existiendo el archivo

Y ¿puedes mirar desde otro ordenador que tenga una conexión a Internet distinta?

Sinceramente estoy que me rindo con este hosting, también está pasando ahora con los archivos php

EDITO: Y ya hice lo que me pediste, probé en otra máquina en la universidad, misma situación, los cambios no se reflejan

EDITO2: También traté subiendo los nuevos archivos desde esta máquina, sin cambios

Puede deberse a que el servidor web (webcindario) esté cacheando los contenidos.

y ante eso que puedo hacer yo para solucionarlo?

Nada, esperar que el servidor se reinicialice luego de una caída (los usuarios de los espacios web no tenemos forma de reinicializarlo).