Yo Dudes and Dudettes for situations calling for more formality.
The last time I read a book about resume writing and cover letters, the examples all said “Dear Hiring Executive”.
Citizen,
Comrade,
or
Homey,
according to circumstances.
Frankly, I’ve always felt a bit weird addressing a total stranger as “Dear”. What moron decreed such a level of intimacy for formal correspondence, anyway?
I generally go with the no salutation, particularly if there’s a RE subject line I can use.
When I do feel the need to salutate, I often use Dear Gentleperson. I’m all about the PC!
Tovarisch:
Hey, Shithead:
My fellow American:
Hey you:
Stella!!!:
Cover letters (and resumes for that matter) are used by potential employers only as a way to quickly place candidates into one of two piles: “Call for an interview” and “don’t bother”. “Quickly” is a key word here; in my experience I’ve never done more than skim a cover letter looking for keywords.
That said, this sorting process relies on quickly identifiable differences. An unusual salutation would be one of those, and so you have to think about whether that’s a difference you want to be judged on. In most cases you don’t; I have yet to find someone point out a salutation other than to say “look what this idiot wrote”; it falls into the category of egregious spelling error, and if noticed can only work against your interests.
I think if this is causing some hand-wringing that omitting the salutation–as Exapno Mapcase suggests–is best; many cover letters don’t have them, so its not something “unusual enough” to be noticed. Otherwise almost any salutation that isn’t lengthy, stilted, or misspelled will be fine. Potential employers will not take a second glance at “Dear Sir” (as opposed to redtail23’s “Dear Gentleperson,” which IMO would leap off the page), and that’s just they way you want it.
I have in front of me a letter from the Ontario Ministry of Revenue, which starts off with my address, including my clearly-masculine name, and then says “Dear Sir/Madam”… 
Things get better afterwards, though; it goes on to say that I do not need to collect and remit provincial sales tax when selling drawings. 
Ooh, not if you’re not sure it’s only men at the company. Most women are not fans of being either (a) ignored or (b) addressed as “gentlemen.”
I would not leave out a salutation. To me that makes it seem like you don’t know how to write a letter.
“Dear” is a convention. There’s no more truth to it than there is to “very truly yours” or “sincerely” when you’re neither of those things either. It’s just how it’s done. Again, omitting the conventions may convey that you’re forward-thinking – but it may also convey that you don’t know how to write a letter.
So here’s another vote for “Dear Madam or Sir” (or “Dear Sir or Madam”). And extra points from me for calling and trying to find a real human being to send it to; that is always preferable.
I usually call or go on-line to get a name. If that doesnt work, I go with Dear Company Name or Dear President/Vice-President/etc.
Dear Sir or Madam, signed yours Faithfully.
This is the convention of writing a formal letter, the definition of a formal letter is one which you do not know to whom it should be addressed.
As in, “Dear sir or madam, would you read my book
It took me years to write, will you take a look?”
Great and powerful Oz,
Start it something like a memo,
Ref: The post of Widget Fiddler you are seeking to fill,
I wish to make my application yadda yadda
You could use this for
Ref - My absolutely huge overdraft of $$$$
or perhaps
Ref - The thong I know you are wearing but don’t admit,