Generally speaking, I keep the text of the error messages in resource files. If you're using .NET 2.0 or higher (Visual Studio 2005 or higher), resource files are automatically compiled into strongly-typed classes, making the code which accesses said messages much more clear and readable.
(EDIT: Having seen another comment which mentions localization, I feel honor-bound to mention it here as well: .NET resource files do an excellent job of localization. You can get the localized text of the resource via the exact same code, with just a few minor tweaks to provide CultureInfo.)
That said, it sounds like a part of this problem domain is a message number. Are these errors being thrown from the database (say, as part of stored procs or triggers)? In that case, then database storage most likely is the right place for them, if only because that documents them most closely to where the "magic numbers" are being used.