Some packages ask for haiku>=r1~beta4_hrev56578_4-1 even with beta3 installed

Are you using a nightly or beta 3? Check the server addresses in HaikuDepot, these must match the system used, see the Haiku Guides.

If you are using a nightly version, you may have just gotten into beta 4 testing.

You can also search for the problem in the bug tracker or file a bug report there.