My employer paid for a branding agency and wound up throwing away most of their names and settling on a name we came up with ourselves. They did give us one good name that I wound up using for a logging tool two years later, so it wasn't a total waste.

I'm of the opinion that if you don't have creative enough people on your team to come up with a good name you probably have bigger problems than the lack of a creative name.

Every startup I've been in paid a naming company. I've never liked the results, but the VCs always have liked the results...