Get previous and next record with two order criteria
select s2.*, @nv NXV, (@nv := id) NNXV from (
select s1.*,
@pv PRV, (@pv := id) NPRV, (@rn := @rn + 1) RN
from (
SELECT DISTINCT profiles.id,
IFNULL(profile_photos.photo_status, 0) photo_status,
IFNULL(profile_photos.photo, 0) photo,
profiles.rnd_order
FROM
`profiles`
LEFT JOIN profile_photos
ON (
  profiles.id = profile_photos.member_id
  AND profile_photos.photo_status = 1
), (select @rn := 0)  RNT
WHERE (profile_photos.photo_status = 1 OR
profile_photos.photo_status is null)
GROUP BY profiles.id
ORDER BY photo_status DESC, profiles.rnd_order DESC) s1
) s2
order by RN desc;


see http://sqlfiddle.com/#!9/409b3/20

you will find the info you wanted in columns NXV and PRV

This fiddle http://sqlfiddle.com/#!9/409b3/47 shows the query for a specific profile id.

select p.*, pf.*,
       pmax.id, pmax.rnd_order,
       pmin.id, pmin.rnd_order
  from profiles p left outer join
       profile_photos pf
       on  pf.member_id = p.id
       and pf.photo_status = 1,
       profiles pmax,
       profiles pmin
  where p.id = 100024
    and pmax.rnd_order = (select ifnull(max(rnd_order),p.rnd_order) from profiles pm where pm.rnd_order &lt; p.rnd_order)
    and pmin.rnd_order = (select ifnull(min(rnd_order),p.rnd_order) from profiles pm where pm.rnd_order &gt; p.rnd_order)
;


Can you check this for performance?  (explain plan looks promising)