Короче говоря, отвечая по пунктам:
1- по гостевой или туристической визе работать нельзя. Для целей поработать нужна "рабочая" виза. "Рабочую2 визу дают, если работа уже найдена и есть трудовой договор или проект оного, которые составляет работодатель (т.е. работу надо найти еще сидя на Украине). Кроме этого трудового договора нужно еще обоснование для АБХ от работодателя, что на это место нет другого СПЕЦИАЛИСТА не из немцев, не из иностранцев, имеющих ПМЖ, не из стран ЕС старых ни новых и т.п... (это грубо, всех тонкостей не знаю). Толъко после этого она может получить визу на работу с последующим ВНЖ с привязкой к этому контракту. Реально такое можно получить, например в области науки. На неквалифицированную работу, естественно, эти возможности не распространяются.
2- что касается залога, то тут, думаю, что-то кто-то путает. Наверное имеется виду Sperkonto: Если приглахсающий в гости не имеет достаточно дохода, чтобы пригласить человека он может открыть здесь (в Германии) специальный счет и положить на него эти 1.500 (по-моему, именно эту сумму) "под приглашение" гостя. Это как залог. Если что, например, гость не покидает вовремя страну, то эти деньги идут на покрытие расходов по его депортации (т.е. приглашающий их теряет). В хорошем случае возращается этот залог приглашаемому через полгода после того как гость покинет страну по предявлению доказательства, что гость страну покинул (например штамп в паспорте гостя о пересечении границы Германии). Но это если приглашающий не имет достаточных доходов, иначе он покрывает все расходы по депортации со своих денег обычным образом и уже неизвестно в какую сумму это вылэтся, - может больше, может менъше.

Кроме того (маленькое отступление по поводу приглашений). Если вы делаете приглашение и даже если она ведет себя послушно и никаких законов не нарушает и т.п., но вдруг заболеет (мало ли что может случиться) и не дай бог попадет в больницу, то не факт что ее туристическая страховка покроет это лечения (обычно это страховки типа от несчастных случаев, - окажут первую помощь и до свиданья) - вы несете и все расходы по лечению. И не известно в какую сумму это выльэтся, - может стоить и не одну тыЩу. Даже если это и покроется страховкой, то это будет потом уже, скорее всего по пребытию на украину и, как я понимаю, возвращена ей (здесь возможны варианты, но такие случаи на форуме тоже описаны).
3- что касается агенств по трудоустройству за рубежом, то как я понимаю в плане Германии это скорее всего программы типа ОП-mädchen, социальный год, DAAD или какие-либо, возможно программы для врачей и т.п. Об агенствах, которые устраивают в гераманию на неквалифицированные работы, - типа мыть столики в ресторанах и т.п., - не слышала. А вот на счет других стран (Греция, например и т.п.) о таких слышала. Но возможно, что-то и есть, но я в это слабо верю. Германия очень строгая страна в этом плане (в Италию, например приехать поработать гораздо проще).