Solidity ecrecover vs Web3j Sign.signMessage() – Compatibility Explained

Using Web3j to sign and verify a message is fine but when I use the signature generated by Web3j to verify using ecrecover in solidity it doesnot seem to work correctly. The signer address is different when executing the solidity code.

On searching for a solution, I found out that newer geth version prepends string "\x19Ethereum Signed Message:\n32" on signing.

Reference here: Totally baffled by ecrecover

I tried to use the solution in reference question but it does not seem to work. My question is what is different with respect to Web3j?
Can anybody familiar with Web3j provide me a working example for message signing and verification?

Here is a simplified version of the contract I was working on:

pragma solidity ^0.4.0;

contract Auth {   

    string public name;

    function Auth(){
        name = "Auth 1.0";
    }

    function verify(bytes32 _message, uint8 _v, bytes32 _r, bytes32 _s) constant returns (address) {
        address signer = ecrecover(_message, _v, _r, _s);
        return signer;
    }

    function verifyWithPrefix(bytes32 _message, uint8 _v, bytes32 _r, bytes32 _s) constant returns (address) {
        bytes memory prefix = "\x19Ethereum Signed Message:\n32";
        bytes32 prefixedHash = sha3(prefix, _message);
        address signer = ecrecover(prefixedHash, _v, _r, _s);
        return signer;
    }
}

Here is the java code using Web3j.

    // Message to sign
    String plainMessage = "hello world";
    byte[] hexMessage = Hash.sha3(plainMessage.getBytes());

    // Use java to sign and verify the signature
    Sign.SignatureData signMessage = Sign.signMessage(hexMessage, ALICE.getEcKeyPair());
    String pubKey = Sign.signedMessageToKey(hexMessage, signMessage).toString(16);
    String signerAddress = Keys.getAddress(pubKey);
    System.out.println("Signer address    : 0x"+ signerAddress);

    // Now use java signature to verify from the blockchain
    Bytes32 message = new Bytes32(hexMessage);
    Uint8 v = new Uint8(signMessage.getV());
    Bytes32 r = new Bytes32(signMessage.getR());
    Bytes32 s = new Bytes32(signMessage.getS());

    String address = contract.verify(message, v, r, s).get().getValue().toString(16);
    String address2 = contract.verifyWithPrefix(message, v, r, s).get().getValue().toString(16);
    System.out.println("Recovered address1 : 0x"+address);
    System.out.println("Recovered address2 : 0x"+address2);