The biggest one is encoding state exclusively in the hypertext communication (what many people would call statelessness). Most web devs aren't comfortable doing away with sessions, but that's just fine as far as HTTP cares.

You could do XML-RPC over HTTP. You could do SOAP over HTTP.

Those would be rather RESTless.

I really don't think SOAP is very ok with HTTP. It misuses the protocol and subverts its goals. For example, version 1 used POST for safe, idempotent requests.