My app started having the same issue too and I am not using library(markdown), instead I am using library(rmarkdown).
The reason you did not have to install anything was because you had the package installed.
I say that because when you use library(markdown) and package is not install, RStudio will prompt you to install it.
I was prompted, installed markdown package, used library(markdown) and went away.
Strange
Update: I commented library(markdown) in my application and it is still running on shinyapp.io
Not sure why it is acting that way