Is it really impossible to protect Android apps from reverse engineering?

The first stop for me would be to optimise and obfuscate the code with ProGuard which is known to work with byte code targeted at Android's Dalvik VM (via Dex). It's a really great tool and can increase the difficulty of 'reversing' your code while shrinking your code's footprint (in some cases dramatically: a recent applet of mine went from about 600 KB down to about 50 KB).

Like others are saying, you will never get 100% security of your algorithm's details while its implementation is being distributed to clients. For that, you'd need to keep the code on your servers alone. Attempts to near 100% percent security for client code effectively amount to DRM and can make your client code fragile in the face of network outages and just generally frustrate (legitimate) users.

The Android developers blog has some useful articles on the matter of 'tamper resistant' Android apps (and they recommend the use of ProGuard as part of the overall approach).

With regards to 'creative' approaches: some developers employ debugger detection techniques to prevent run-time analysis and combine this with encryption of portions of binary code (to deter static analysis), but to be honest, a determined enough attacker can circumvent these, while it can cause legitimate user frustration as illustrated by the Windows KB article Games: Error Message: A Debugger Has Been Detected: Unload the Debugger and Try Again. My girlfriend's 'Learn to drive' DVD software will not run under VirtualBox for this reason, but she blames Linux of course!

OpenRCE and Wikipedia's article on obfuscated code may be good starting points if you want to look into this further. But be warned, you may lose more through over zealous use of these techniques frustrating your users than you would through loss of trade secrets by reverse engineering. Like Anton S says, maybe the most 'creative' approach lies with tweaking the business model rather than the technology.

The latest Android SDK update on 6th Dec 2010 (coinciding with Android 2.3 Gingerbread release):

Integrated ProGuard support: ProGuard is now packaged with the SDK Tools. Developers can now obfuscate their code as an integrated part of a release build.

If it's a possibility: remote procedure calls to a well-protected server (the server has the code you want to protect).

Make it so cheap to bother and don't build your business model on top of secrets that are executed on the client side. In other words, don't share your secrets.

It is impossible to protect any client side code from reverse engineering. You can just use more or less efficient ways of obfuscating your code. And optimized x86 assembler happens to be a pretty good obfuscation.

So if you have algorithmic secrets put them on the server-side.

How to lock compiled Java Classes to prevent decompilation

You can't. Any scheme can be defeated by someone with sufficient skills, time and motivation.

(Incidentally, this also applies to software that is compiled to binary. The only difference is in the amount of effort involved in decompiling.)

My question is how one would go about protecting an app that contains algorithmic trade secrets from reverse-engineering?

Simply don't install the app on the user's phone. Or (more usefully), run the code that contains the trade secrets on a remote (properly secured) server.