As a self-employed in Albania, I want to have a business-to-business (b2b) relation (I will sell them my service) with an Austrian company. Does the Austrian company have to pay VAT in Austria for my payment? If that is the case, is this 100% deductable from taxes?
No. Albania is not yet in the EU and thus a third Country.
Dependant upon the rules for charging VAT in Albania, your invoice for services to an Austrian company will more than likely have to include the appropriate tax which the Austrian Company will account for in their general taxes as gross business expense - not VAT. Albania may consider that, within their rules - an invoice to a third country is not a VATable event so no tax may need to be added to the invoice. You should check this with your local (Albanian) Customs office. If no VAT is chargeable, then no VAT is payable by the Austrian company to you but you may need to still record the value of the sale in the appropriate place on your VAT return in order to record the turnover.
When (and if) Albania accedes to the EU, the rules will of course change. You will need the Austrian Company's EU VAT registration number in order to avoid charging them VAT on your services (and you will record it accordingly as a EU sale) but that may be a long time off yet.
The nett effect will be the same but of course there will be an impact on cash flow since they will not be able to recover the business expense in the VAT cycle but in their tax cycle.