Guys, thanks for all the suggestions.
Tried the bleach and vinegar (as well as nail polish remover) methods already.
Had 3 different lengths of the stained hoses soaked in 3 containers of the above mentioned solutions for 3 whole days; unfortunately to no avail...
Turbokeu mentioned
trichlorethylen, that sounds greek to me...
Any layman terms for that and can it be gotten from pharmacies off the shelf?