SOAP messages in REST based web service

Disclaimer: I am really confused between REST and SOAP based services.
After reading many tutorials (which seems contradictory to each other) on REST based web service I was wondering whether we can/should use SOAP to send/receive messages in REST based web service ?
I tried following links
1) http://www.ibm.com/developerworks/webservices/library/ws-restful/

2) http://rest.elkstein.org/2008/02/how-simple-is-rest.html

By "SOAP based services" I assume you are meaning WS-I Basic Profile web services. The distinction is important because SOAP can be used with REST as well as WS-I BP web services. Let me explain.

SOAP is an XML based messaging format for exchange of data. Soap also defines a means for making remote procedure calls. SOAP is an open standard from the W3C. SOAP is agnostic about the underlying transport layer. Frequently HTTP is used as a transport layer, but it can happily run over SMTP and TCP, and other transports too.

REST is an architectural style (not a standard), so be careful not to compare REST and SOAP directly because you are not comparing apples with apples. REST takes HTTP and uses it is the way it was meant to be used, with all its subtleties and richness. The REST architectural style can used to transfer data in any format - it does not mandate any particular data format. So SOAP is a perfectly good serialization format for a REST style web service. But many people use JSON, XML, plain text and many other formats with REST. You can happily exchange binary data over REST too, like image files. The nice thing is you get to choose the data format that makes most sense for your application.

Note that since REST is a pattern, not a standard, there is a lot of debate about what it means to be truely RESTful. There is a concept called the Richardson Maturity Model which lays out a series of steps towards the REST ideal. By comparing with Richardson's model we can see exactly how RESTful a particular REST implementation is. WS-I BP web services are at Level 0 on this scale (ie. not very RESTful at all, just using HTTP as a dumb transport layer).

I would say this about choosing REST vs WS-I Basic Profile web services - it depends on your audience. If you are developing a B2B type interface within an enterprise, it is more common to see WSI-BP web services. Because there is an underlying standard, and because of the mature support by enterprise vendors (such as IBM, Oracle, SAP, Microsoft) and because of the level of framework support particularly in .NET and Java, WSI-BP makes a lot of sense when you need to get something going quickly and you want to make it easy for clients to connect in an enterprise environment, and the data being exchanged is business data that serializes nicely as SOAP.

On the other hand if you are exposing web services to the wider web audience, I would say there has been a trend away from WSI-BP and towards the RESTful style. Because REST only assumes the client supports HTTP, it can be made to interoperate with the widest possible audience. REST also gives you the scalability of the web itself, with the support for caching of resources etc which makes it will scale up to a large audience much better than WSI-BP web services.