I Googled my idea and found another company that has been doing the same thing for a few years. It's for somewhat of a niche market, but everyone I talk to (including potential clients) says it's a great idea and they've never heard of it. So it seems like there should be plenty of room for me to grab a share of the market.
Lots of answers here say don't worry about if someone else steals your idea. You've got to do a good enough job executing your idea that it doesn't matter if someone takes it. What about being on the other side? Does it make sense for me to pursue this or to look for something truly novel?
A few examples come to mind of companies who came along and did something that had already been done, but did it better. Google is at the top of that list. Web search existed long before they started doing it! A smaller example would be agilezen.com who created an online lean project management tool and seem to be doing well even though there are other sites that do similar things.
I already know that my pricing structure will be different than that other company, but I don't know which pricing model customers will prefer. Mine is consumption based while theirs is a flat monthly fee. It seems like with the buzz around "cloud computing" that the consumption based model is gaining in popularity with SaaS products.
The other thing I noticed is that their website isn't very easy to navigate and looks like it was built 5 years ago and not updated. I can definitely create a better web experience than what they have.
The other thought I've had is that the existence of a company doing the same thing proves that it's a viable business. Are there any other factors that I should consider?