If you’re charged UK VAT and the invoice shows a GBnnnnn VAT number then you can treat it the same as a UK supplier and record and reclaim the VAT as usual.
If you’ve been charged the supplier’s home country VAT then that’s not reclaimable unless you are yourself VAT registered in the same country. This suggests they’re treating you as a consumer rather than as a business customer, if you can convince them you’re a business then they might re-issue the invoice without VAT and let you reverse charge it.
If you contact them and give them your VAT number, they should then issue invoices without VAT. Either way, if you receive a service from an overseas supplier, then you must account for the output and input VAT under the reverse charge scheme. If you have been charged VAT, this will not be UK VAT (unless as @ian_roberts points out they also have a UK VAT number in which case you just treat it as a UK supplier) and therefore you cannot recover it. You would calculate the reverse charge VAT on the total amount paid.