Yes, they could use the old password as long as they have the old wallet file (If the same private keys are there of course).
Meaning what? If I wanted to prevent this I would have to change my password, then create a new bitcoin address and send all the bitcoins to the new address?
How does one prevent that most easily?
You didn't mention the wallet used here, some of them generate different addresses and still keep the private keys in one wallet.dat file. Again, If you think that someone have access to your old wallet.dat file + he might be able to get the password you should make a new wallet file (and not a new address only) with a new password and send everything there instead of just changing the password.
Simple steps to follow (whatever wallet you are using):
1. Install Mycelium in your android.
2. Run your wallet (from PC) and send all funds to your Mycelium.
3. Remove the old wallet and create a new one
4. Send from Mycelium to your new generated wallet on PC.