As you have seen, doing the parsing on the device can be troublesome with data use and also potential network access issues (what if you don't have a connection at the time you try to search?). Doing this work on a server with a more reliable internet connection is a good idea. You will be using Google Cloud Messaging (GCM) not C2DM which is deprecated. You don't need to buy special hardware to host a server, and if it's only for your use, an always-on desktop computer could do the work for you. Since you'll be using push, you don't even need a static IP address (or a domain name) for the server, since the device will never 'phone home', since you just need a notification when things change.
I would first start by opening a port on my desktop computer and try to get the device to talk to your machine via your LAN.
Hope this helps.