Существует ли какой-нибудь (возможно, ОС) встраиваемый файл механизма БД на основе (например, Firebird или SQLite), который может работать в приложении Meidum Trust ASP.NET? Любое решение no-sql для того же сценария?
Вы должны попросить вашего хостинг-провайдера установить вашу любимую встроенную БД в GAC, которая может работать.
SQL Server Compact должен работать в среде Medium Trust.
см. http://msdn.microsoft.com/en-us/library/gg606540.aspx