IMHO для поиска нормальной квартиры план утопичный, здесь только неходовые квартиры так предлагаются.
А что за фирма работу предлагает? Некоторые, обычно крупные фирмы и с жильем помогают, могут сами с нормальным маклером связаться, который действительно квартиру найти поможет, а не только провизион за те кв., которые через него сдают кассирует (что характерно для этих мест), не все, но некоторые фирмы даже услуги маклера оплатить готовы.
Альтернативно можно не стремиться переехать прямо к началу работы, а найти на месяц-другой комнату/квартиру как Pendler (кста, опять таки, работодатель вполне месяц-другой ее и оплатить и найти может). А уже будучи на месте вечерами/в перерыв постоянное жилье искать.
Еще один вариант: квартиры от Baugenossenschaften (Например, http://wohnungsbaugenossenschaften-bw.de/customsearch.php?landkreis=03) у них бывают неплохие квартиры и недорого, вместо маклерских надо на определенную сумму части покупать, но освобождая квартиру их вроде продать можно. Обычно у них можно заполнить анкету и записаться в очередь, чтобы сообщили, если подходящая квартира освободится.
Да, Sindelfingen и Böblingen практически слиты территориально, нет разницы в каком из них снимать, на велосипеде/машине все очень близко.