Australian publisher Dark Prints Press has an open call for novella submissions. They're particularly interested in dark crime, mystery, and thriller submissions at this time. The reading period is short with the deadline of December 21. Their next reading period for novellas is June. The word count is 15,000 to 40,000 words. For ebooks the payment is an AUD$75 advance and 30% of royalties. Print is $100 AUD advance and 20% of royalties. You can check out the press here
UPDATE: February 9, 2015 This market has disappeared into the ether.