Fortunately, Plan B does not work on Android 3.1+, as tested on a XOOM and a Galaxy Nexus.
What Plan B does is exploit a security hole that could be used by drive-by malware, which is specifically why Android prevents it from happening anymore.
UPDATE
To clarify: As inazaruk posted and I put into comments on other answers, all applications, upon installation, are placed in a "stopped" state. This is the same state that the application winds up in after the user force-stops the app from the Settings application. While in this "stopped" state, the application will not run for any reason, except by a manual launch of an activity. Notably, no BroadcastReceviers will be invoked, regardless of the event for which they have registered, until the user runs the app manually.
This block covers the Plan B scenario of remote-install-and-run, which they were taking advantage of previously. After all, with that, anyone with a hacked Google account would be at risk of having their device infected, hands-free as it were.
So, when the OP says:
I need to start a Service as soon as the Applicaton gets installed on the Device
the OP will be unsuccessful and will need to redesign the application to avoid this purported "need".
