Darren,
You are probably wasting your time with phone calls like that, the scrap of paper he wrote your name and number on are probably in the bin by now!
You are far better off calling them and asking for a contact name for their contracts manager, then write to him/her and enclose a business card with your letter. If they are looking for cleaning services they will contact you, if not then at the very least they will keep your card in their index system and may give you a call if they are let down.
I did this and got a call nearly two years later from a company who had been let down by their contract cleaners, they asked us if we could do a sparkle clean that afternoon.
We did it for them, 4 people on a £750K property and now have the contracts for three of their sites in Northumberland and we've been asked to quote for more sites in the Durham area.