BUY new sand or go no sand not having a sand bed has huge benefits. the tank will be cleaner and be much easier to clean. the only thing sand is good for is to look at and IMO
90% of the time sand looks like junk. DO NOT use the sand that was in the tank before it will be a nightmare. I would strongly suggest this esspecially beings you said you like your tank clean. This makes it very easy to clean the tank. also it is much better for corals. all a sand bed does is help trap Phosphates because the food and waste falls in it and the sand "eats" it and leaves behind phosphates that leach into the system. With a bare bottom tank you just siphon all the gunk out every week and it doesnt rot away. Promotes coral growrth by keeping nitrates and phosphates down. and bosting another type of phosphate (cant rember the name) that aids to coral growth and isnt harmful.
Vinigar should remove that algae stain without issue.