Proper mySQL Statement for Searching Availability Dates

It's not going to work unless you start with a normalized database - your current schema makes no sense - presumably a home can have multiple bookings - yet you appear to have booking_id as a foreign key in the home table referencing bookings - this should be the other way around (booking should reference home_id).

Using the correct schema:

SELECT home.*
FROM home h
WHERE NOT EXISTS (
   SELECT 1 FROM booking b
   WHERE b.end_date>$start_time
   AND b.start_date<$end_time
   AND b.home_id=h.home_id
);

or

SELECT home.*
FROM home h 
LEFT JOIN booking b
ON (b.home_id=h.home_id
   AND b.end_date>$start_time
   AND b.start_date<$end_time
)
WHERE b.home_id IS NULL;

With an index on booking (start_time, end_time, home_id) it should be reasonably efficient.

SELECT H.home_id, H.name, H.address, H.location
FROM Home H
LEFT JOIN (SELECT booking_id
           FROM booking
           WHERE @fromdate BETWEEN fromdate AND todate
           OR @todate BETWEEN fromdate AND todate) B
ON H.booking_id = B.booking_id
WHERE B.booking_id IS NULL