Books or bookshop vouchers, vouchers to places they might not think to go (eg CERES in Melbourne - sorry, can’t think of something in Perth), something regularly used but gourmet (like the olive oil suggestion), tickets to events (like galleries or wine/cheese tasting), an unusual t-shirt or 2 (eg from redbubble, but only if you know their taste well enough)