AFAIK, the Application object uses a Hashtable for storing the key-value pairs, and it is generally very fast for accessing. Application variables are kept in memory, but when the the application is recycled so are the application variabales. You could check when accessing, re-read the objects and restore in Application, if the application has been recycled. Alternatively, read the objects in the Application_Start event handler in Global.asax.
Otherwise, the Cache is your best bet, especially if you're reading from SQL Server as the other poster, points out.