Bluetooth: Android->Arduino wrong characters transmitted

Thanks for your suggestion johnwasser.

I tried to play around with the AT commands, but this is a bit messy, as I can't find any documentation
for this specific module.
As it did not respond to AT+UART? command (the one where I could configure parity and stop bits)
I downloaded the following code I found in the forum (just modified slightly):

/*
  Set Up a JY-MCU Bluetooth Dongle. Version 1.0
  
  http://dx.com/p/jy-mcu-arduino-bluetooth-wireless-serial-port-module-104299?item=6
  http://byron76.blogspot.com/2011/09/one-board-several-firmwares.html
  
  It's a very simple and inexpensive Bluetooth Serial Module. 4-Pin connection: 5V, GND, TX, RX.
  You can configure the NAME, PIN, and BAUD using this utility, settings are stored in the
  module firmware until you modify them again.
  
  This utility will search for the bluetooth module on all the possible BAUD options, then configure
  the module according to the configuration parameters below:
  
  Note: You can only configure the module when it does not have an active bluetooth connection!
  
  Jeff Simpson
  jeffsimpson@alum.wpi.edu
*/

#include <SoftwareSerial.h>


/* Beginning of Configuration Section */

// NAME maximum of 20 characters
char NAME[21] = "MyRobot";

// 4 digit numeric pin
char PIN[5] = "4444";
SoftwareSerial btConnection(10,11);
/*
  character code for BAUD
  1 for 1200 bps 
  2     2400 bps
  3     4800 bps 
  4     9600 bps 
  5    19200 bps 
  6    38400 bps 
  7    57600 bps 
  8   115200 bps 
  9   230400 bps 
  A   460800 bps 
  B   921600 bps 
  C  1382400 bps
  */
char BAUD='8';

/* End of Configuration Section */

char response[21]; // Storage for responses from module
int rv=0; // return value
int found=0; // module found

void setup() {
  
  // Open Serial Port for display
  Serial.begin(115200);
  Serial.print("Searching for BT Dongle");
  
  // Search for bluetooth module on all 12 possible baudrates
  long baud[12] = {1200, 2400, 4800, 9600, 19200, 38400, 57600, 115200, 230400, 460800, 921600, 1382400};
  for(int a = 0; a < 12; a++)
  {
    btConnection.begin(baud[a]);
    btConnection.write("AT"); // "AT" will respond with "OK" if it is working
    delay(100);
    while(btConnection.available() < 0);
    btConnection.readBytes(response, 2);
    Serial.println(response);
    if (strncmp(response, "OK", 2) == 0)
    {
      Serial.print("\nBluetooth Module found at BAUD ");
      Serial.println(baud[a]);
      found=1;
      break;
    }
    else
    {
      Serial.print(".");
      //Serial.println(baud[a]);
    }
  }
  if (found==0)
  {
    Serial.println("\nERROR: Blueooth Module not found!");
    Serial.println("Make sure there are no active bluetooth connections and try again");
    while(1);
  }
  delay(100);

  btConnection.write("AT+VERSION"); // Check the firmware version, because we can
  while(btConnection.available() < 0);
  btConnection.readBytes(response,2);
  if (strncmp(response, "OK", 2)==0)
  {
    rv = btConnection.readBytes(response, 20);
    response[rv] = 0;
    Serial.print("BT Module Firmware Version: ");
    Serial.println(response);
  }
  else
  {
    Serial.println("Error checking BT Version");
  }
  delay(100);
  
  btConnection.write("AT+NAME"); // Set the bluetooth device name
  btConnection.write(NAME);
  while(btConnection.available() < 0);
  btConnection.readBytes(response,9);
  if (strncmp(response, "OKsetname", 9)==0)
  {
    Serial.print("Setting Name: ");
    Serial.println(NAME);
  }
  else
  {
    Serial.println("Error Setting Bluetooth Name");
  }
  delay(100);
  
  btConnection.write("AT+PIN"); // Set the PIN
  btConnection.write(PIN);
  while(btConnection.available() < 0);
  btConnection.readBytes(response, 8);
  if (strncmp(response,"OKsetPIN", 8)==0)
  {
    Serial.print("Setting PIN: ");
    Serial.println(PIN);
  }
  else
  {
    Serial.println("Error Setting Bluetooth PIN");
    Serial.println(response);
  }
  delay(100);
  
  btConnection.write("AT+BAUD"); // Set the BAUD
  btConnection.write(BAUD);
  while(btConnection.available() < 0);
  btConnection.readBytes(response, 2);
  if (strncmp(response, "OK", 2)==0)
  {
    rv = btConnection.readBytes(response, 7);
    response[rv] = 0;
    Serial.print("Setting BAUD: ");
    Serial.println(response);
  }
  else
  {
    Serial.println("Error Setting Bluetooth BAUD");
    Serial.println(response);
  }
  Serial.println("Bluetooth Setup Completed");
}

void loop() {
}

My output is the following:

Searching for BT Dongle
.
.
.
.
.
.
.Oé
.Oé
.Oé
.Oé
.Oé
.
ERROR: Blueooth Module not found!
Make sure there are no active bluetooth connections and try again

So instead of OK I recieve .
But I am sure I correctly recieved OK some time ago.
What could cause such an issue?