Ruth:It has been reported that it is going to change in Ukraine, but I'm not sure about the date

Unless things are changing, I believe that the Russian and Ukrainian rail systems don't allow booking more than 45 days prior to departure.
Not that long ago (since February) UZ changed it, now booking during regular time (not when schedules are about to change) available 90 days in advance. It started with major trains and directions (like Kyiv-Lviv/Donestsk/Odesa/Dnipropetrovsk/Kharkiv), but I think they plan to introduce the same 90 days in advance rule for all the long-distance trains eventually.

40 days prior to the date I want to go, still no trains... Any idea?
What you mean no trains? For June 12 I see already plenty of trains on route Kyi-Lviv (at least almost all the afternoon and evening ones, meaning with departure from 15 to 23). Only new daytime express trains aren't there yet, but they still aren't there for any UZ route
First of all thank you for your help... There are some connections on http://www.e-kvytok.com.ua and it is possible to book although I am not able to understand Ukrainian (most of the fields are almost self-explanatory)... But there is another huge problem and I am started to get panicked, because they free benches are running out: It seems, that http://www.e-kvytok.com.ua does not accept Western credit cards (I read about this problem in the forefield)... So any ideas? At least: Could you recommend a trustworthy (and not too expensive) agency?

There were few cases that non-Ukrainian card weren't accepted (it was about some 3D Secure issue or something like that), but at the same time there were many people who succeeded with US and EU cards, so I guess you just need to try and see. Btw, one of the processing centers you can pay with e-kvytok is via Ukrainian branch of Raiffesen bank, so obviously, in your case, Austrian Raiffesen bank card should work fine, at least it seems like it should if to compare it to any other western card.
About Ukrainian and e-kvytok besides google translate you can always get an Engilsh guide on how to use it (for instance http://europetrainsguide.com/Advice/How-to-Buy-Train-Tickets/Ukraine-UZ.html ) or try to rely on a new version of e-kvytok (http://www.e-kvytok.org.ua/eng ), though it's seems still to be in testing mode, meaning not everything works yet (at least for me)
Thank you, the guide you posted is a bit more precise than the one I used...
Nevertheless I do not understand the payment options, which are described as following:
"Next you will need to select via which Bank processing centre you want to make payment. For international bank cards suitable only a) 'Raiffeisen-Aval' Bank and b) 'Finanсу & Credit' Bank. After you made a choice, click 'Оформлення документів' (Processing of Documents) button."
When I am using a Visa credit card which is from a banking institution different from Raiffeisen-Aval, I have to use option b)? Or is "Financy & Credit' Bank" a bank establishment too and I can't use any (VISA) credit cards from other banking institutions (like UniCredit, Paribas, HBSC,...)?

When I am using a Visa credit card which is from a banking institution different from Raiffeisen-Aval, I have to use option b)? Or is "Financy & Credit' Bank" a bank establishment too and I can't use any (VISA) credit cards from other banking institutions (like UniCredit, Paribas, HBSC,...)?
As far as I understand, it's either or option, both Raiffeisen-Aval and Financy & Credit Bank accept all types of bank cards (including international), it is just e-kvytok gives you the choice via which bank to pay. So you can pay with your card either via Raiffeisen-Aval or Financy & Credit Bank, no difference. The only difference is that when paying via Raiffeisen-Aval you can switch to English (or German, which might be better option for you) at the payment page