Ausländeramt & rent contracts

You do not need to show a rental contract when registering, but a "Wohnungsgeberbescheinigung" form filled and signed by the landlord.
Since you must register after a week or two, the landlord must sign the form even for such short bookings. But experience has shown that most hotels, servioced apartments and other short-term options are unwilling to do it, so be prepared for problems!

On reading again, I am not sure I understood your question correctly:
Registration is done at the town hall or "Bürgerbüro", not at the Ausländeramt (which is only in charge of visa, residence permit, etc.). Since the local Ausländeramts usually need booked appointments weeks in advance and work very slowly, your approach will not work in dealing with them (unless you only move around within the realm of one local Ausländeramt - they are usually in charge of a whole city).

Hi Beppi, thanks for your helpful reply.

We'll probably stop at least a month at the first point, before deciding whether to move on.

Is it the Bürgerbüro that I will be after then for registration of intention to stay >90 days then? Is it worth booking in advance when booking accommodation (do they accept that?).

We'll probably do a long stay in an AirBnB, as the plan is not to move over furniture etc in the first phase, but to do that once a bit more settled (probably beyond month 3 or 6). Do you think they will be happy to sign the Wohnungsgeberbescheinigung?

Can you download the Wohnungsgeberbescheinigung or is it only obtainable in hard copy from the local offices?

Many thanks
Mark

The Wohnungsgeberbescheinigung is available online.
Of course I don‘t know if your specific landlord would have any problem signing it. It‘s probably worth asking before you book.
You will have to deal with the Ausländeramt as well, if you come on a residence visa or want to apply for one here. As I said they are slow, inefficient and not at all set up to deal with situations such as yours.