「RESTful」と「REST」の違いってなんでしょうか?
Wikipediaには、以下のような記載がありました。

http://ja.wikipedia.org/wiki/REST
FieldingのREST原則に従うシステムは、しばしばRESTfulといわれる。

ちゃんとRESTの原則に従って実装されているシステムのことを、RESTfulと呼ぶようです。
ということはちゃんとしていないRESTもあるということです。
ちゃんとしたREST(つまりRESTful)については、Wikipediaの説明やRESTful Webサービスが詳しいです。

今現在、多数のWebAPIが国内で公開されていますが、そのほとんどがREST形式であると自称している(もしくはREST形式と一般に認知されています)。ですがそのほとんどは、HTTPプロトコルに対してXML形式の結果を返しているだけで、完全なRESTとはいえない「なんちゃってREST」であるような気がします。
例えば、Yahoo!Japanのデベロッパーネットワークには、RESTの説明として以下のような記載があります。

http://developer.yahoo.co.jp/glossary/#qt

REST
REpresentational State Transferの略語。HTTPリクエストに対してXMLをレスポンスとして返す。Yahoo! JAPANの提供するすべてのWeb APIで利用可能です。

当時からこういった説明をするサービスが多かったこともあり、RESTといえば「HTTPリクエストに対してXMLレスポンスを返すもの」という認識が一般に広まり、普通に使用されるようになってしまった感があります。

そういった経緯のせいかどうかはわかりませんが、RESTに忠実な実装を行ったシステムのことをRESTfulと呼ぶようになり、なんとなく棲み分けができて、めでたしめだたし?となっているようです。

※そもそもRESTfulがWebAPIのアーキテクチャとしてベストかというと、そうでもないケースも多いです。RESTfulは、リソース指向的な考えに基づいたアーキテクチャなので、何かしらの処理を関数的に実行させたい場合などは、RPC(Remote Procedure Call)的に呼び出せる「なんちゃってREST」の方が適しているケースも多いように思います。

※「なんちゃってREST」なAPIについては、「POX(Plain Old Xml) over HTTP」や「XML over HTTP」と言った呼び方をする動きもありましたが、あまり一般的にはならなかったようです。

3/20:追記


RESTful Webサービスのyoheiさんからはてぶでコメントもらいました。

RESTは名詞。RESTful は形容詞

なるほど。なるほど。