How can I determine what other solutions might exist in this space?
Exhaust the obvious places. Start with simple Google searches, learn about the relevant companies, find out who they consider to be competitors (can be gleamed from their news/public announcements/win announcements), learn about those companies too. Look for visible employees of said companies on LinkedIn, and check out their work history.
Once you're comfortable, locate and speak to an investment banker or VC that is working in this area. Ask them intelligent, open ended, questions based on your research to help you gain more knowledge of the field.
Is it reasonable to approach potential customers, let them know of my experience in this area, and try to gauge their interest in at least trying this product when it's ready?
Yes. This is a standard activity to take as part of market research. Talented salesmen combine this with an actual sales pitch - sometimes even getting customers to sign on and commit to buying the product before it's been built (more often, before it's finished). Obtaining this kind of information will help you shape the product better, might net you a mentor or advisor who can help better direct your work, and looks good when trying to speak with potential investors or partners/employees.
Finally, if the ideas behind my product are based upon other projects I may have done as an employee or consultant, do I need to get any legal advice before getting started?
Your knowledge is your own, so generally speaking, if you're building everything from scratch based on what you know how to do, you're in the clear. Major items to worry about are non-compete like clauses (which may or may not be relevant, even if they were not explicitly included in your contract, based on where you live and /or worked, consult a lawyer to be sure) and patents/IP owned by the companies (you may have learned of tools and techniques which are covered by patents the companies own, and may end up owing royalties). IP/patents shouldn't really be a legal problem, though - it's usually a red herring, or more of a business issue. If you're building something interesting enough to be worth an IP fight, then, if you do get sued, you'll be able to adjust your business model to either pay to handle the lawsuit, or pay for the royalties.