So can I accomplish my task (send recorded audio to webservice and then play back response from webservice) without a voice shield?
No. The microcontroler / arduino board is not design to work with sound. You need additional hardware, mic + preamplifier + memory ( 10 seconds phone quality sound require 80 k byte, about 10 times more than mega board has, and 40 times more than uno ), this is why I recommended to look for voice shield. My advice , split your design in a few subsystems, and look for solution in each category.
1. Audio frond end.
- Voice shield, or
- Mic + preamp.
2. Analog digital converter and radio link.
- Arduino + wi-fi shield, plus wi-fi (already existed) on receiver side;
- Zigbee (pair) plus arduino on other end connected to PC.
- something else.
3. Voice recognition.
Look for shield that capable to do it. What I recommend above isn't design for this task.
May be this one:http://www.ewerksonline.com/catalog/product_info.php?products_id=203
I don't have device and can't comment.