[US Only] A lot of people miss this, but if the company you're researching is registered as a legal entity (company name ending in "LLC," "Inc.," or "Corporation") - you'll be able to find their filing information in the state where the entity is registered. The easiest way is to google "<state> entity search" and plug in their company name. Some states will even show you scans of their filing information. Use this information to find out how long they've been in business and corroborate it with what they say when you ask.
Going through the process of setting up a legal entity with separate bank accounts takes time, and if someone is looking for a quick buck they're less likely to go through that process.
Another way to see if they're legitimate is if they process credit cards themselves. Merchant processing accounts and business bank accounts usually require credit checks and require a decent amount of paperwork, rather than taking 5 minutes to set up a PayPal account. This is another way to see how legitimate the company is.
If they're using WHMCS, you can append "cart.php?licensedebug&forceremote" to the end of their domain to see when it was registered, and to also see if their WHMCS install is pirated or legitimate.
Of course this won't help you steer clear from all the bad guys, but it'll eliminate many of them and make you more informed.
The discussion that was sparked by this post was moved and can be continued via this thread