Is it ever possible to have both security and deniability? Aren't they kind of intrinsically opposed?

I mean, is the same argument to keep security off your home wifi router so that if the MPAA goes after you for seeding torrents, you can claim that it might've been the neighbour.

There's something in-between, though it doesn't actually break the paradox, just makes some different tradeoffs:

In cryptography, a ring signature is a type of digital signature that can be performed by any member of a group of users that each have keys. Therefore, a message signed with a ring signature is endorsed by someone in a particular group of people. One of the security properties of a ring signature is that it should be difficult to determine which of the group members' keys was used to produce the signature

http://en.wikipedia.org/wiki/Ring_signature

On the IM side of things, you should check out OTR (off-the-record messaging): https://otr.cypherpunks.ca/ - in particular check out the top 4 goals mentioned on that page.

Really interesting. I've used OTR but didn't realize those goals.

However, I don't quite understand how "anyone can forge messages after the conversation" works. Can you explain any more?

The keys are effectively public once the conversation ends -- they aren't tied to your identity. So those messages could have been forged by anyone, there's no proof they came from you.

You need to narrow the question. Instead ask "Is deniability hard in store-and-forward or and storage applications?"

The answer is yes. But, as others here have pointed out, you can use ephemeral keys for some applications.