As far as I know, TeamCity NuGet Server is subject to the artifact cleanup policy defined in "Administration | Project-related Settings | Build History Clean-up", so make sure your package is still there!!
My personal advise is ALWAYS setup a dedicated nuget server. You can setup one for free simply cloning the official NugetGallery project on GitHub: that's the same codebase used by nuget.org so you'll have a familiar UI and increased performances (NugetGallery leverage Lucene.NET indexing capabilities).