Most Efficient Way to... Unique Random String
Create a table with a big pool of 5-character strings that are added in sequence (so they are unique), and have a GUID as their primary key. Add a column to indicate whether they are used or not.
When you need a new number, you select top 1 from the pool, order by the guid (so it becomes random), and set the result as "spent".
Is randomness more important, or is uniqueness more important? -- note that I said "more" important; I get the fact that you need both.
If randomness is more important, then you're going to need some way to track historical values. The database itself (with an appropriate index) is going to be the best way to do this.
If uniqueness is more important, then simply use a counter and zero-pad it to five digits. This will, of course, limit you to 100,000 rows, so you could alternatively use a counter and a transformation into character space (eg, 1 = "A", 2 = "B", 27 = "AA", and so on).